A Riemannian perspective on matrix recovery and constrained optimization
<p>Nonlinear matrix recovery is an emerging paradigm in which specific classes of high-rank matrices can be recovered from an underdetermined linear system of measurements. In particular, we consider matrices whose columns, seen as data points, belong to an algebraic variety, namely, a set def...
| Glavni autor: | |
|---|---|
| Daljnji autori: | |
| Format: | Disertacija |
| Jezik: | English |
| Izdano: |
2021
|
| Teme: |
| _version_ | 1826307177672867840 |
|---|---|
| author | Goyens, F |
| author2 | Cartis, C |
| author_facet | Cartis, C Goyens, F |
| author_sort | Goyens, F |
| collection | OXFORD |
| description | <p>Nonlinear matrix recovery is an emerging paradigm in which specific classes of high-rank matrices can be recovered from an underdetermined linear system of measurements. In particular, we consider matrices whose columns, seen as data points, belong to an algebraic variety, namely, a set defined by finitely many polynomial equations. The nonlinear structure is exploited using an appropriately chosen feature map, which induces a low-rank structure in the feature space, thus allowing recovery of the original (high-rank) matrix. The same framework is applicable to matrices whose columns are divided in clusters, so that we can address clustering tasks with missing entries.</p>
<p>We formulate the rank minimization of the feature matrix as the minimization of a smooth cost function on a Riemannian manifold, which then allows us to employ the theoretically rigorous Riemannian optimization framework, that calls on differential geometry tools to construct feasible iterative algorithms on specific Riemannian manifolds. In particular, we show the potential benefits of using second-order algorithmic variants --- instead of first-order ones --- as they are able to achieve recovery of the original data with high accuracy. We additionally develop an alternating minimization method to solve the recovery problem, for which we give convergence and complexity guarantees.</p>
<p>Considering algebraic varieties also leads us to propose a new approach for the denoising of point clouds that approximately fit such structures, as well as for their registration, namely, the task of estimating a transformation which overlaps two point clouds representing the same shape in different coordinate systems.</p>
<p>Finally, we consider general optimization problems with smooth equality constraints. Due to the challenge of achieving feasibility for generic nonlinear equality constraints, we must depart from the Riemannian framework and we propose an infeasible algorithm which minimizes a smooth penalty function, known as Fletcher's augmented Lagrangian. We provide optimal worst-case bounds on the number of iterations that are required to find an approximate first- and second-order critical point.</p> |
| first_indexed | 2024-03-07T06:59:01Z |
| format | Thesis |
| id | oxford-uuid:ff19cd3e-0119-4de7-b4e5-6535ff0f1edf |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:59:01Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:ff19cd3e-0119-4de7-b4e5-6535ff0f1edf2022-03-27T13:42:00ZA Riemannian perspective on matrix recovery and constrained optimizationThesishttp://purl.org/coar/resource_type/c_db06uuid:ff19cd3e-0119-4de7-b4e5-6535ff0f1edfNumerical analysisEnglishHyrax Deposit2021Goyens, FCartis, CEftekhari, A<p>Nonlinear matrix recovery is an emerging paradigm in which specific classes of high-rank matrices can be recovered from an underdetermined linear system of measurements. In particular, we consider matrices whose columns, seen as data points, belong to an algebraic variety, namely, a set defined by finitely many polynomial equations. The nonlinear structure is exploited using an appropriately chosen feature map, which induces a low-rank structure in the feature space, thus allowing recovery of the original (high-rank) matrix. The same framework is applicable to matrices whose columns are divided in clusters, so that we can address clustering tasks with missing entries.</p> <p>We formulate the rank minimization of the feature matrix as the minimization of a smooth cost function on a Riemannian manifold, which then allows us to employ the theoretically rigorous Riemannian optimization framework, that calls on differential geometry tools to construct feasible iterative algorithms on specific Riemannian manifolds. In particular, we show the potential benefits of using second-order algorithmic variants --- instead of first-order ones --- as they are able to achieve recovery of the original data with high accuracy. We additionally develop an alternating minimization method to solve the recovery problem, for which we give convergence and complexity guarantees.</p> <p>Considering algebraic varieties also leads us to propose a new approach for the denoising of point clouds that approximately fit such structures, as well as for their registration, namely, the task of estimating a transformation which overlaps two point clouds representing the same shape in different coordinate systems.</p> <p>Finally, we consider general optimization problems with smooth equality constraints. Due to the challenge of achieving feasibility for generic nonlinear equality constraints, we must depart from the Riemannian framework and we propose an infeasible algorithm which minimizes a smooth penalty function, known as Fletcher's augmented Lagrangian. We provide optimal worst-case bounds on the number of iterations that are required to find an approximate first- and second-order critical point.</p> |
| spellingShingle | Numerical analysis Goyens, F A Riemannian perspective on matrix recovery and constrained optimization |
| title | A Riemannian perspective on matrix recovery and constrained optimization |
| title_full | A Riemannian perspective on matrix recovery and constrained optimization |
| title_fullStr | A Riemannian perspective on matrix recovery and constrained optimization |
| title_full_unstemmed | A Riemannian perspective on matrix recovery and constrained optimization |
| title_short | A Riemannian perspective on matrix recovery and constrained optimization |
| title_sort | riemannian perspective on matrix recovery and constrained optimization |
| topic | Numerical analysis |
| work_keys_str_mv | AT goyensf ariemannianperspectiveonmatrixrecoveryandconstrainedoptimization AT goyensf riemannianperspectiveonmatrixrecoveryandconstrainedoptimization |