EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2163. Alternating Projections Methods for Matrix Completion: Regularized and Inexact Projections
Invited abstract in session MA-34: Optimization and learning for data science and imaging (Part I), stream Advances in large scale nonlinear optimization.
Monday, 8:30-10:00Room: 43 (building: 303A)
Authors (first author is the speaker)
| 1. | Mattia Silei
|
| Dipartimento di Matematica ed Informatica "Ulisse Dini", Università degli Studi di Firenze | |
| 2. | Stefania Bellavia
|
| Dipartimento di Ingegneria Industriale, Universita di Firenze | |
| 3. | Simone Rebegoldi
|
| Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Università di Modena e Reggio Emilia |
Abstract
Matrix Completion (MC) involves reconstructing the missing entries of a partially observed matrix M by leveraging the assumption that M has low rank [1]. Problems that can be approached with MC arise in various fields, such as recommendation systems, image inpainting, and compressed sensing. Our work starts from the idea of reformulating MC as the problem of finding a matrix in the intersection of two sets: the set of matrices with the same observed entries as M, and the nonconvex set of matrices of rank less than or equal to r. This is a feasibility problem (FP), which generally involves finding a point x in the intersection of two sets A and B. Since the 1950s [2], the Alternating Projection Method (APM) has been proposed to solve FP. Starting from a point in B, APM generates a sequence of points by alternately projecting onto A and B. We will discuss two theoretically well founded regularized variants of the method, employing exact projections (RAPM) and inexact projection onto the set B (iRAPM). The obtained theoretical results guided us to the definition of a new stopping criterion for the Krylov iterative method employed for computing the approximate truncated SVD (nedeed to compute the inexact projection onto the rank set). Some numerical experiments to validate the convergence results and the performance of the studied methods will be also shown.
[1] Candès E. J. et al., Found. Comput. Math., 9, 717--772, 2009
[2] Von Neumann J., Functional Operators, 1951
Keywords
- Continuous Optimization
- Mathematical Programming
- Algorithms
Status: accepted
Back to the list of papers