“Nyström method”的意思、由来-开放百科全书

词条

Nyström method

释义

Discretization of the integral
Example
Sampling for Nyström method
Minimum Sum of Squared Similarities Sampling (MSSS)
References

In numerical analysis, the Nyström method^[1] 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 discrete intervals; quadrature or numerical integration determines the weights and locations of representative points for the integral.

The problem becomes a system of linear equations with equations and unknowns, and the underlying function is implicitly represented by an interpolation using the chosen quadrature rule. This discrete problem may be ill-conditioned, depending on the original problem and the chosen quadrature rule.

Since the linear equations require operations to solve, high-order quadrature rules perform better because low-order quadrature rules require large for a given accuracy. Gaussian quadrature is normally a good choice for smooth, non-singular problems.

Discretization of the integral

Standard quadrature methods seek to represent an integral as a weighed sum in the following manner:

where are the weights of the quadrature rule, and points are the abscissas.

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 a 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^[2] that this approach increase the speed of the clustering on large datasets.

References

1. ^{{cite journal|last=Nyström|first=Evert Johannes|title=Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben |journal=Acta Mathematica |year=1930|volume=54|issue=1|pages=185–204|doi=10.1007/BF02547521}}
2. ^{{citation | last1 = Bouneffouf | first1 = Djallel | last2 = Birol | first2 = Inanc | contribution = Sampling with Minimum Sum of Squared Similarities for Nystrom-Based Large Scale Spectral Clustering | pages = 2313–2319 | publisher = AAAI Press | title = Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, {IJCAI} 2015, Buenos Aires, Argentina, July 25–31, 2015 | volume = 8834 | year = 2015 | url = http://ijcai.org/papers15/Abstracts/IJCAI15-327.html | isbn = 978-1-57735-738-4}}

Leonard M. Delves & Joan E. Walsh (eds): Numerical Solution of Integral Equations, Clarendon, Oxford, 1974.
Hans-Jürgen Reinhardt: Analysis of Approximation Methods for Differential and Integral Equations, Springer, New York, 1985.

3 : Integral equations|Numerical analysis|Numerical integration (quadrature)

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。