Nonlinear matrix recovery using optimization on the Grassmann manifold
We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the ori...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2022
|
| _version_ | 1826314796675366912 |
|---|---|
| author | Goyens, F Cartis, C Eftekhari, A |
| author_facet | Goyens, F Cartis, C Eftekhari, A |
| author_sort | Goyens, F |
| collection | OXFORD |
| description | We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by a constrained non-convex optimization problem involving the Grassmann manifold. We propose two sets of algorithms, one arising from Riemannian optimization and the other as an alternating minimization scheme, both of which include first- and second-order variants. Both sets of algorithms have theoretical guarantees. In particular, for the alternating minimization, we establish global convergence and worst-case complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we show that the alternating minimization converges to a unique limit point. We provide extensive numerical results for the recovery of union of subspaces and clustering under entry sampling and dense Gaussian sampling. Our methods are competitive with existing approaches and, in particular, high accuracy is achieved in the recovery using Riemannian second-order methods. |
| first_indexed | 2024-03-07T08:07:35Z |
| format | Journal article |
| id | oxford-uuid:131fdc4f-47e7-4997-aeaf-bd72c67011fe |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:11:10Z |
| publishDate | 2022 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:131fdc4f-47e7-4997-aeaf-bd72c67011fe2024-10-14T14:28:12ZNonlinear matrix recovery using optimization on the Grassmann manifoldJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:131fdc4f-47e7-4997-aeaf-bd72c67011feEnglishSymplectic ElementsElsevier2022Goyens, FCartis, CEftekhari, AWe investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by a constrained non-convex optimization problem involving the Grassmann manifold. We propose two sets of algorithms, one arising from Riemannian optimization and the other as an alternating minimization scheme, both of which include first- and second-order variants. Both sets of algorithms have theoretical guarantees. In particular, for the alternating minimization, we establish global convergence and worst-case complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we show that the alternating minimization converges to a unique limit point. We provide extensive numerical results for the recovery of union of subspaces and clustering under entry sampling and dense Gaussian sampling. Our methods are competitive with existing approaches and, in particular, high accuracy is achieved in the recovery using Riemannian second-order methods. |
| spellingShingle | Goyens, F Cartis, C Eftekhari, A Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title | Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title_full | Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title_fullStr | Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title_full_unstemmed | Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title_short | Nonlinear matrix recovery using optimization on the Grassmann manifold |
| title_sort | nonlinear matrix recovery using optimization on the grassmann manifold |
| work_keys_str_mv | AT goyensf nonlinearmatrixrecoveryusingoptimizationonthegrassmannmanifold AT cartisc nonlinearmatrixrecoveryusingoptimizationonthegrassmannmanifold AT eftekharia nonlinearmatrixrecoveryusingoptimizationonthegrassmannmanifold |