|
==Mathematical definition==
Hamm and Huang<ref>Keaton Hamm and Longxiu Huang. Perspectives on CUR decompositions. Applied and Computational Harmonic Analysis, 48(3):1088–1099, 2020.</ref> givesand theAldroubi followinget theoremal.<ref>@article{aldroubi2019cur, describingtitle={CUR decompositions, similarity matrices, and subspace clustering}, author={Aldroubi, Akram and Hamm, Keaton and Koku, Ahmet Bugra and Sekmen, Ali}, journal={Frontiers in Applied Mathematics and Statistics}, volume={4}, pages={65}, year={2019}, publisher={Frontiers Media SA}</ref> describe the basicsfollowing theorem, which ofoutlines a CUR decomposition of a matrix <math>L</math> with rank <math>r</math>:
Theorem: Consider row and column indices <math>I, J \subseteq [n]</math> with <math>|I|, |J| \ge r</math>. Denote submatrices <math>C = L_{:,J},</math> <math>U = L_{I,J}</math> and <math>R = L_{I,:}</math>. If rank(<math>U</math>) = rank(<math>L</math>), then <math>L = CU^+R</math>, where <math>(\cdot)^+</math> denotes the [[Moore–Penrose pseudoinverse]].
Denote submatrices <math>C = L_{:,J},</math> <math>U = L_{I,J}</math> and <math>R = L_{I,:}</math>.
If rank(<math>U</math>) = rank(<math>L</math>), then <math>L = CU^+R</math>, where <math>(\cdot)^+</math> denotes the [[Moore–Penrose pseudoinverse]].
In other words, if <math>L</math> has low rank, we can take a sub-matrix <math>U = L_{I,J}</math> of the same rank, together with some rows <math>R</math> and columns <math>C</math> of <math>L</math> and use them to reconstruct <math>L</math>.
|
