In numerical analysis, the Nyström method or quadrature method seeks the numerical solution of an integral equation by replacing the integral with a representative weighted sum. The continuous problem is broken into
Contents
- Discretization of the integral
- Example
- Sampling for Nystrm method
- Minimum Sum of Squared Similarities Sampling MSSS
- References
From the n solved points the function value at other points is interpolated consistent with the chosen quadrature method. Depending on the original problem and the choice of quadrature the problem may be ill-conditioned.
Since the linear equations require
Discretization of the integral
Example
Applying this to the inhomogeneous Fredholm equation of the second kind
results in
Sampling for Nyström method
The most important step of the Nyström method is sampling, because different sampled landmark points give different approximations of the original matrix.
Uniform sampling without replacement: is the most used approach for this purpose, where every point has the same probability of being included in the sample.
Minimum Sum of Squared Similarities Sampling (MSSS)
MSSS is an non-uniform sampling approach that considers both the variance and the similarity of the data distribution in its sampling data, which approximately maximizes the determinant of the reduced similarity matrix that represents the mutual similarities between sampled data points. It is shown in that this approach increase the speed of the clustering on large datasets.