Nyström Method
A Nyström Method is a numerical analysis method that ...
- See: Gaussian Quadrature, Symmetric Positive Semidefinite Matrix, Integral Equation, Numerical Integration, System of Linear Equations.
References
2019
- (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Nyström_method Retrieved:2019-10-14.
- 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 [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ n }[/math] equations and [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ O(n^3) }[/math] operations to solve, high-order quadrature rules perform better because low-order quadrature rules require large [math]\displaystyle{ n }[/math] for a given accuracy. Gaussian quadrature is normally a good choice for smooth, non-singular problems.
- 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 [math]\displaystyle{ n }[/math] discrete intervals; quadrature or numerical integration determines the weights and locations of representative points for the integral.
2014
- (Wang et al., 2014) ⇒ Shusen Wang, Chao Zhang, Hui Qian, and Zhihua Zhang. (2014). “Improving the Modified Nyström Method Using Spectral Shifting.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623614
- QUOTE: The Nystrom method is an efficient approach to enabling large-scale kernel methods. The Nystrom method generates a fast approximation to any large-scale symmetric positive semidefinite (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nystrom approximation is low-rank, when the spectrum of the SPSD matrix decays slowly, the Nystrom approximation is of low accuracy. In this paper, we propose a variant of the Nystrom method called the modified Nystrom by spectral shifting (SS-Nystrom).