Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Low-rank matrix approximations
open-in-new
<h2 id="nystrm-approximation">Nyström approximation</h2> <p><a href="/facts/Kernel_method/fYuURIPk">Kernel methods</a> become computationally unfeasible when the number of points D {\displaystyle D} is so large such that the kernel matrix K {\displaystyle K} cannot be stored in memory. </p><p>If D {\displaystyle D} is the number of training examples, the <a href="/facts/Algorithmic_efficiency/VutjvPTd">storage and computational cost</a> required to find the solution of the problem using general <a href="/facts/Kernel_method/fYuURIPk">kernel method</a> is O ( D 2 ) {\displaystyle O(D^{2})} and O ( D 3 ) {\displaystyle O(D^{3})} respectively. The Nyström approximation can allow a significant speed-up of the computations.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> This speed-up is achieved by using, instead of the kernel matrix, its <i>approximation</i> K ~ {\displaystyle {\tilde {K}}} of <a href="/facts/Rank_(linear_algebra)/Yp9b5LK3">rank</a> d {\displaystyle d} . An advantage of the method is that it is not necessary to compute or store the whole kernel matrix, but only a submatrix of size d × D {\displaystyle d\times D} . </p><p>It reduces the storage and complexity requirements to O ( D d ) {\displaystyle O(Dd)} and O ( D d 2 ) {\displaystyle O(Dd^{2})} respectively. </p><p>The method is named "Nyström approximation" because it can be interpreted as a case of the <a href="/facts/Nystr%25C3%25B6m_method/VSrN1S3U">Nyström method</a> from <a href="/facts/Integral_equation/LCu4Imfq">integral equation</a> theory.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h3>Kernel approximation</h3> <p><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>: 357 <a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>Consider a <a href="/facts/Positive-definite_kernel/Ws3zkxfl">positive-definite kernel</a> function k : X × X → R {\displaystyle k:X\times X\to \mathbb {R} } . Given some data points x 1 , x 2 , … , x D {\displaystyle x_{1},x_{2},\dots ,x_{D}} , we can form the kernel matrix K ∈ R D × D {\displaystyle K\in \mathbb {R} ^{D\times D}} such that K i j := k ( x i , x j ) {\displaystyle K_{ij}:=k(x_{i},x_{j})} . </p><p>Now, let d ∈ 1 : D {\displaystyle d\in 1:D} be an integer, then we can divide the kernel matrix as K = [ K 11 K 12 K 21 K 22 ] ∈ R D × D {\textstyle K={\begin{bmatrix}K_{11}&K_{12}\\K_{21}&K_{22}\end{bmatrix}}\in \mathbb {R} ^{D\times D}} , where K 11 ∈ R d × d {\textstyle K_{11}\in \mathbb {R} ^{d\times d}} is the top-left corner of it. Also, set C = [ K 11 K 21 ] {\textstyle C={\begin{bmatrix}K_{11}\\K_{21}\end{bmatrix}}} to be its first d {\displaystyle d} columns. </p><p>The Nyström approximation of K {\displaystyle K} in this case is K ~ = C K 11 + C T = [ K 11 K 21 ] K 11 + [ K 11 K 12 ] {\displaystyle {\tilde {K}}=CK_{11}^{+}C^{T}={\begin{bmatrix}K_{11}\\K_{21}\end{bmatrix}}K_{11}^{+}{\begin{bmatrix}K_{11}&K_{12}\end{bmatrix}}} where K 11 + {\displaystyle K_{11}^{+}} is the <a href="/facts/Moore%25E2%2580%2593Penrose_inverse/CU73tntq">Moore–Penrose pseudoinverse</a> of K 11 {\displaystyle K_{11}} , which must exist since K 11 {\displaystyle K_{11}} is positive semidefinite. </p> <h3>Properties</h3> <p>By <a href="/facts/Mercer%2527s_theorem/6CmBHnHc">Mercer's theorem</a>, we can decompose the kernel matrix as a <a href="/facts/Gram_matrix/SGb2VGTU">Gram matrix</a>: K = X T X {\textstyle K=X^{T}X} , where X ∈ R N × D {\textstyle X\in \mathbb {R} ^{N\times D}} . Let X ′ {\textstyle X'} be the left d {\textstyle d} columns of X {\textstyle X} . </p> <p>Theorem—We have </p> <ol><li> K ~ = [ K 11 K 12 K 21 K 21 K 11 + K 12 ] {\displaystyle {\tilde {K}}={\begin{bmatrix}K_{11}&K_{12}\\K_{21}&K_{21}K_{11}^{+}K_{12}\end{bmatrix}}} </li> <li>The Nyström approximation K ~ {\textstyle {\tilde {K}}} is the unique matrix that is symmetric, has the same first d {\textstyle d} columns as K {\textstyle K} , and has column space spanned by the first d {\textstyle d} columns of K {\textstyle K} .</li> <li> K ~ = ( P X ) T ( P X ) {\textstyle {\tilde {K}}=(PX)^{T}(PX)} , where P {\textstyle P} is the projection matrix that orthogonally projects to the space spanned by the first d {\textstyle d} columns of X {\textstyle X} .</li> <li> K ~ {\textstyle {\tilde {K}}} is positive semidefinite.</li> <li>If rank ( K 11 ) = rank ( K ) {\textstyle \operatorname {rank} (K_{11})=\operatorname {rank} (K)} , then K ~ = K {\textstyle {\tilde {K}}=K} .</li></ol> <h3>Regularized least squares</h3> <p>In a vector and kernel notation, the problem of <a href="/facts/Regularized_least_squares/h62zhD8J">regularized least squares</a> can be rewritten as: min c ∈ R n 1 n ‖ Y − K c ‖ R n 2 + λ ⟨ c , K c ⟩ R n . {\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|Y-Kc\|_{\mathbb {R} ^{n}}^{2}+\lambda \langle c,Kc\rangle _{\mathbb {R} ^{n}}.} Computing the gradient and setting in to 0, the minimum can be obtained: − 1 n K ( Y − K c ) + λ K c = 0 ⇒ K ( K + λ n I ) c = K Y ⇒ c = ( K + λ n I ) − 1 Y , where c ∈ R n {\displaystyle {\begin{aligned}&-{\frac {1}{n}}K(Y-Kc)+\lambda Kc=0\\\Rightarrow {}&K(K+\lambda nI)c=KY\\\Rightarrow {}&c=(K+\lambda nI)^{-1}Y,{\text{ where }}c\in \mathbb {R} ^{n}\end{aligned}}} The inverse matrix ( K + λ n I ) − 1 {\displaystyle (K+\lambda nI)^{-1}} can be computed using <a href="/facts/Woodbury_matrix_identity/bcmjY73W">Woodbury matrix identity</a>: ( K + λ n I ) − 1 = 1 λ n ( 1 λ n K + I ) − 1 = 1 λ n ( I + K n , q ( λ n K q ) − 1 K n , q T ) − 1 = 1 λ n ( I − K n , q ( λ n K q + K n , q T K n , q ) − 1 K n , q T ) {\displaystyle {\begin{aligned}(K+\lambda nI)^{-1}&={\frac {1}{\lambda n}}\left({\frac {1}{\lambda n}}K+I\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I+K_{n,q}({\lambda n}K_{q})^{-1}K_{n,q}^{\text{T}}\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I-K_{n,q}(\lambda nK_{q}+K_{n,q}^{\text{T}}K_{n,q})^{-1}K_{n,q}^{\text{T}}\right)\end{aligned}}} It has the desired storage and complexity requirements. </p> <h2 id="randomized-feature-maps-approximation">Randomized feature maps approximation</h2> <p class="note">Main article: <a href="/facts/Random_feature/vF0Ufdgg">Random feature</a></p> <p>Let x , x ′ ∈ R d {\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}} – samples of data, z : R d → R D {\displaystyle z:\mathbb {R} ^{d}\to \mathbb {R} ^{D}} – a randomized feature map (maps a single vector to a vector of higher dimensionality) so that the inner product between a pair of transformed points approximates their <a href="/facts/Kernel_method/fYuURIPk">kernel</a> evaluation: </p><p> K ( x , x ′ ) = ⟨ Φ ( x ) , Φ ( x ′ ) ⟩ ≈ z ( x ) T z ( x ′ ) , {\displaystyle K(\mathbf {x} ,\mathbf {x'} )=\langle \Phi (\mathbf {x} ),\Phi (\mathbf {x'} )\rangle \approx z(\mathbf {x} )^{\text{T}}z(\mathbf {x'} ),} where Φ {\displaystyle \Phi } is the mapping embedded in the <a href="/facts/Radial_basis_function_kernel/A88JLBJF">RBF kernel</a>. </p><p>Since z {\displaystyle z} is low-dimensional, the input can be easily transformed with z {\displaystyle z} , after that different linear learning methods to approximate the answer of the corresponding nonlinear kernel can be applied. There are different randomized feature maps to compute the approximations to the RBF kernels. For instance, random Fourier features and random binning features. </p> <h3>Random Fourier features</h3> <p>The random Fourier features map produces a <a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo</a> approximation to the feature map. The Monte Carlo method is considered to be randomized. These <i>random features</i> consists of sinusoids cos ( w T x + b ) {\displaystyle \cos(w^{\text{T}}\mathbf {x} +b)} randomly drawn from <a href="/facts/Fourier_transform/XXhKJtc8">Fourier transform</a> of the <a href="/facts/Kernel_method/fYuURIPk">kernel</a> to be approximated, where w ∈ R d {\displaystyle w\in \mathbb {R} ^{d}} and b ∈ R {\displaystyle b\in \mathbb {R} } are <a href="/facts/Random_variable/TwTBXnLT">random variables</a>. The line is randomly chosen, then the data points are projected on it by the mappings. The resulting scalar is passed through a sinusoid. The product of the transformed points will approximate a shift-invariant kernel. Since the map is smooth, random Fourier features work well on interpolation tasks. </p> <h3>Random binning features</h3> <p>A random binning features map partitions the input space using randomly shifted grids at randomly chosen resolutions and assigns to an input point a binary bit string that corresponds to the bins in which it falls. The grids are constructed so that the probability that two points x , x ′ ∈ R d {\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}} are assigned to the same bin is proportional to K ( x , x ′ ) {\displaystyle K(\mathbf {x} ,\mathbf {x'} )} . The inner product between a pair of transformed points is proportional to the number of times the two points are binned together, and is therefore an unbiased estimate of K ( x , x ′ ) {\displaystyle K(\mathbf {x} ,\mathbf {x'} )} . Since this mapping is not smooth and uses the proximity between input points, Random binning features works well for approximating kernels that depend only on the <a href="/facts/L1_distance/zU7gGUPv"> L 1 {\displaystyle L_{1}} distance</a> between datapoints. </p> <h2 id="comparison-of-approximation-methods">Comparison of approximation methods</h2> <p>The approaches for large-scale kernel learning (<a href="/facts/Nystr%25C3%25B6m_method/VSrN1S3U">Nyström method</a> and random features) differs in the fact that the Nyström method uses data dependent basis functions while in random features approach the basis functions are sampled from a distribution independent from the training data. This difference leads to an improved analysis for kernel learning approaches based on the Nyström method. When there is a large gap in the <a href="/facts/Spectrum_of_a_matrix/BIBnA4qf">eigen-spectrum</a> of the <a href="/facts/Kernel_method/fYuURIPk">kernel</a> matrix, approaches based on the Nyström method can achieve better results than the random features based approach.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Nystr%25C3%25B6m_method/VSrN1S3U">Nyström method</a></li> <li><a href="/facts/Support_vector_machine/XobxpdBG">Support vector machine</a></li> <li><a href="/facts/Radial_basis_function_kernel/A88JLBJF">Radial basis function kernel</a></li> <li><a href="/facts/Regularized_least_squares/h62zhD8J">Regularized least squares</a></li></ul> <h2 id="external-links">External links</h2> <ul><li>Andreas Müller (2012). <a href="http://peekaboo-vision.blogspot.de/2012/12/kernel-approximations-for-efficient.html">Kernel Approximations for Efficient SVMs (and other feature extraction methods)</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Bach, Francis R.; Jordan, Michael I. (7–11 August 2005). Predictive low-rank decomposition for kernel methods. International Conference on Machine Learning. Bonn Germany: ACM Press. pp. 33–40. doi:10.1145/1102351.1102356. ISBN 978-1-59593-180-1. <a href="978-1-59593-180-1" target="_blank">978-1-59593-180-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Williams, C.K.I.; Seeger, M. (2001). "Using the Nyström method to speed up kernel machines". Advances in Neural Information Processing Systems. 13. <a href="http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines" target="_blank">http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Williams, C.K.I.; Seeger, M. (2001). "Using the Nyström method to speed up kernel machines". Advances in Neural Information Processing Systems. 13. <a href="http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines" target="_blank">http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Drineas, Petros; Mahoney, Michael W. (2005), Auer, Peter; Meir, Ron (eds.), "Approximating a Gram Matrix for Improved Kernel-Based Learning", Learning Theory, vol. 3559, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 323–337, doi:10.1007/11503415_22, ISBN 978-3-540-26556-6, retrieved 20 January 2025 <a href="978-3-540-26556-6" target="_blank">978-3-540-26556-6</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Drineas, Petros; Mahoney, Michael W. (2005), Auer, Peter; Meir, Ron (eds.), "Approximating a Gram Matrix for Improved Kernel-Based Learning", Learning Theory, vol. 3559, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 323–337, doi:10.1007/11503415_22, ISBN 978-3-540-26556-6, retrieved 20 January 2025 <a href="978-3-540-26556-6" target="_blank">978-3-540-26556-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Bach, Francis R.; Jordan, Michael I. (7–11 August 2005). Predictive low-rank decomposition for kernel methods. International Conference on Machine Learning. Bonn Germany: ACM Press. pp. 33–40. doi:10.1145/1102351.1102356. ISBN 978-1-59593-180-1. <a href="978-1-59593-180-1" target="_blank">978-1-59593-180-1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2018). Foundations of machine learning. Adaptive computation and machine learning (Second ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-03940-6. <a href="978-0-262-03940-6" target="_blank">978-0-262-03940-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Gittens, Alex; Mahoney, Michael W. (3 June 2013), Revisiting the Nystrom Method for Improved Large-Scale Machine Learning, arXiv:1303.1849 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin and Zhi-Hua Zhou (2012). "Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison". Advances in Neural Information Processing Systems 25 (NIPS). <a href="http://papers.nips.cc/paper/4588-nystrom-method-vs-random-fourier-features-a-theoretical-and-empirical-comparison.pdf" target="_blank">http://papers.nips.cc/paper/4588-nystrom-method-vs-random-fourier-features-a-theoretical-and-empirical-comparison.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> </ol>