Finding a low-rank basis in a matrix subspace
For a given matrix subspace, how can we find a basis that consists of low-rank matrices? This is a generalization of the sparse vector problem. It turns out that when the subspace is spanned by rank-1 matrices, the matrices can be obtained by the tensor CP decomposition. For the higher rank case, th...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer Verlag
2016
|
| _version_ | 1826304929318305792 |
|---|---|
| author | Nakatsukasa, Y Soma, T Uschmajew, A |
| author_facet | Nakatsukasa, Y Soma, T Uschmajew, A |
| author_sort | Nakatsukasa, Y |
| collection | OXFORD |
| description | For a given matrix subspace, how can we find a basis that consists of low-rank matrices? This is a generalization of the sparse vector problem. It turns out that when the subspace is spanned by rank-1 matrices, the matrices can be obtained by the tensor CP decomposition. For the higher rank case, the situation is not as straightforward. In this work we present an algorithm based on a greedy process applicable to higher rank problems. Our algorithm first estimates the minimum rank by applying soft singular value thresholding to a nuclear norm relaxation, and then computes a matrix with that rank using the method of alternating projections. We provide local convergence results, and compare our algorithm with several alternative approaches. Applications include data compression beyond the classical truncated SVD, computing accurate eigenvectors of a near-multiple eigenvalue, image separation and graph Laplacian eigenproblems. |
| first_indexed | 2024-03-07T06:25:10Z |
| format | Journal article |
| id | oxford-uuid:f4079a45-2be7-4240-a5fb-3cb13a4b770f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:25:10Z |
| publishDate | 2016 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | oxford-uuid:f4079a45-2be7-4240-a5fb-3cb13a4b770f2022-03-27T12:16:42ZFinding a low-rank basis in a matrix subspaceJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f4079a45-2be7-4240-a5fb-3cb13a4b770fEnglishSymplectic Elements at OxfordSpringer Verlag2016Nakatsukasa, YSoma, TUschmajew, AFor a given matrix subspace, how can we find a basis that consists of low-rank matrices? This is a generalization of the sparse vector problem. It turns out that when the subspace is spanned by rank-1 matrices, the matrices can be obtained by the tensor CP decomposition. For the higher rank case, the situation is not as straightforward. In this work we present an algorithm based on a greedy process applicable to higher rank problems. Our algorithm first estimates the minimum rank by applying soft singular value thresholding to a nuclear norm relaxation, and then computes a matrix with that rank using the method of alternating projections. We provide local convergence results, and compare our algorithm with several alternative approaches. Applications include data compression beyond the classical truncated SVD, computing accurate eigenvectors of a near-multiple eigenvalue, image separation and graph Laplacian eigenproblems. |
| spellingShingle | Nakatsukasa, Y Soma, T Uschmajew, A Finding a low-rank basis in a matrix subspace |
| title | Finding a low-rank basis in a matrix subspace |
| title_full | Finding a low-rank basis in a matrix subspace |
| title_fullStr | Finding a low-rank basis in a matrix subspace |
| title_full_unstemmed | Finding a low-rank basis in a matrix subspace |
| title_short | Finding a low-rank basis in a matrix subspace |
| title_sort | finding a low rank basis in a matrix subspace |
| work_keys_str_mv | AT nakatsukasay findingalowrankbasisinamatrixsubspace AT somat findingalowrankbasisinamatrixsubspace AT uschmajewa findingalowrankbasisinamatrixsubspace |