234. Three Alternating Projection Methods for Matrix Completion
Invited abstract in session TC-3: Theoretical and algorithmic advances in large scale nonlinear optimization and applications Part 2, stream Large scale optimization: methods and algorithms.
Tuesday, 14:00-16:00Room: B100/4011
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
A Feasibility Problem (FP) consists of finding a point in the intersection of two sets. Since the 1950s [1], the Alternating Projection Method (APM) has been used to solve FP, and more recently a regularized version has been proposed. In the first part of our work, we design inexactness criteria to extend the regularized version to use inexact projection onto one of the sets, and describe a practical procedure to implement the criteria. In the second part, we introduce the Matrix Completion (MC) problem, which consists of reconstructing the missing entries of a partially observed matrix M by leveraging the assumption that M has low rank [2]. Then, we show how MC can be formulated as a FP, and describe how implement inexactness criteria check in the case of the rank level set, which is a nonconvex set. In particular, it consists of a new stopping criterion for the Lanczos method used for the truncated SVD computation. Finally, we present numerical experiments to compare the three variants of AP on the task of MC with both random matrices and matrices from applications.
[1] Von Neumann J. Functional Operators (AM-22), Volume 2: The Geometry of Orthogonal Spaces, 1951
[2] Cand`es E. J. and Recht B., Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), pp. 717–772.
Keywords
- Large-scale optimization
- Computational linear algebra
Status: accepted
Back to the list of papers