An inexact alternating projection method with application to matrix completion

Stefania Bellavia, Simone Rebegoldi, Mattia Silei · 2025

Read An inexact alternating projection method with application to matrix completion by Stefania Bellavia, Simone Rebegoldi, Mattia Silei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19224.txt.

Introduction

Bellavia, Rebegoldi, and Silei develop a new algorithm for nonconvex feasibility problems in a 2025 mathematics paper. Their method is an inexact alternating projection method with regularization. It allows one of the two projections to be done only approximately, under set rules.

The authors prove that the method converges globally when a merit function meets a stated property. They then apply it to affine rank minimization, which includes matrix completion. A Krylov solver approximates the needed singular value step, with stopping rules drawn from the solver itself. Tests on matrix completion problems support the method. The design avoids wasted work from solving steps too exactly.

Catalog record

CREATORStefania Bellavia, Simone Rebegoldi, Mattia Silei
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19224

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An inexact alternating projection method with application to matrix completion Stefania Bellavia, Simone Rebegoldi, Mattia Silei Abstract We develop and analyze an inexact regularized alternating projection method for nonconvex feasibility problems. Such a method employs inexact projections on one of the two sets, according to a set of well-defined conditions. We prove the global convergence of the algorithm, provided that a certain merit function satisfies the Kurdyka-Łojasiewicz property on its domain. The method is then specialized to the class of affine rank minimization problems, which includes matrix completion as a special case. We approximate the truncated Singular Value Decomposition of the matrix that has to be projected by means of a Krylov solver, and provide suitable stopping criteria for the Krylov method complying with the theoretical inexactness conditions. The information needed to implement such stopping criteria do not require an extra computational effort as they are a by-product of the Krylov method itself and avoid the so called oversolving phenomena. Results of the numerical validation of the algorithm on matrix completion problems are presented. keywords affine rank minimization, alternating projections, inexact projections, krylov subspaces, matrix completion 1 Introduction This paper is concerned with regularized alternating projection methods for computing a point in the intersection of two nonconvex sets A and B , namely \text{find }x\text{ such that }x\in A\cap B\quad\quad A,B\subset\mathbb{R}^{n}. (1.1) The alternating projection method (APM) dates back to the seminal paper von Neumann 2010 by J. von Neumann in 1950. Starting from a point in the first set, APM generates a sequence of points by alternately projecting onto the two sets. The method converges globally when A,B are convex Bauschke and Borwein 1996 , and a rich literature has been devoted to the convergence analysis of APM in the convex case Bauschke and Borwein 1993 ; Bauschke et al. 1997 ; Bauschke and Borwein 1996 ; Escalante and Raydan 2011 ; Behling et al. 2021 . When one of the sets is nonconvex, APM converges only locally and further hypotheses on the sets and their intersection are required Drusvyatskiy 2013 ; Drusvyatskiy et al. 2015 ; Lewis and Malick 2008 ; Lewis et al. 2009 ; Noll and Rondepierre 2016 . 1.1 Contribution of the paper We focus on a regularized variant of APM (RAPM) proposed in Attouch et al. 2010 , for which global convergence holds even in the case of nonconvex sets. RAPM requires exact projections on both sets; hence, it is not applicable when the projection on one of the sets is exact , while it is not possible or too expensive to compute the exact projection onto the other set. We design a theoretically well-founded inexact variant of RAPM, denoted by iRAPM, that allows to use inexact projections on the latter set. Inspired by Birgin et al. 2003 ; Ferreira et al. 2022 ; Bonettini et al. 2023 , we introduce suitable conditions that the inexact projection has to satisfy in order to preserve the theoretical properties of the exact counterpart RAPM. Our main motivation for this study lies in the application of alternating projection methods to Matrix Completion (MC) problems and, more generally, affine rank minimization problems, which consist in finding a matrix Z\in\mathbb{R}^{n_{1}\times n_{2}} of minimum rank that satisfies a given system of linear equations: \displaystyle\min \displaystyle\textrm{rank}(Z), (1.2) \displaystyle\textrm{s.t. }{\cal A}(Z)=b, where {\cal A}:\mathbb{R}^{n_{1}\times n_{2}}\rightarrow\mathbb{R}^{q} is a linear map and b\in\mathbb{R}^{q} . Problem ( 1.2 ) encompasses the MC problem, system identification and control problems, Euclidean embedding, and collaborative filtering Recht et al. 2010 . Assuming to know the sought rank of the matrix Z , say r , we reformulate the affine rank minimization problem as the problem of finding a matrix in the intersection of two sets: the set \mathcal{C} of matrices satisfying the linear constraints and the rank level set , that is, the nonconvex set \mathcal{C}_{r} of matrices of rank less than or equal to r . Then, we specialize APM, RAPM and iRAPM to this latter class of problems. First, we show that the two sets \mathcal{C} and \mathcal{C}_{r} satisfy the assumptions that guarantee the convergence of the three methods , thus providing a theoretical support to the employment of APMs for solving affine rank minimization problems. Second, we focus on the computation of the projection onto the rank level set, namely the truncated Singular Value Decomposition (SVD) of the matrix that has to be projected. This is carried out by an iterative method, with an inherent truncation error. In the large scale setting, this is an expensive task and iterative Krylov methods are used Saad 2011 in order to avoid full matrix factorizations. Suitable stopping criteria for this inner iterative process are therefore of crucial importance in order to save Krylov inner iterations, while preserving the same convergence properties as RAPM. We propose novel stopping criteria for the Krylov method that comply with the theoretical conditions imposed in iRAPM. The information needed to implement such stopping criteria does not require extra computational effort as it is a by-product of the Krylov method itself. Some numerical experiments on matrix completion problems to validate the convergence results, the proposed stopping criteria and the performance of the studied methods will be also shown. 1.2 Related works Early general results on inexact APM schemes in Kruger and Thao 2016 emerge naturally from the convergence theory of the exact algorithm, but their application to common feasibility problems is not investigated. In the works Díaz Millán et al. 2021 ; Drusvyatskiy and Lewis 2019 , inexact APMs are proposed for problems where, similarly to our setting, the projection onto one of the two sets can be computed exactly while the other projection is inexact. On the one hand, in Díaz Millán et al. 2021 , the authors propose an APM where the projection onto one of the sets is approximately computed by means of the conditional gradient method. On the other hand, in Drusvyatskiy and Lewis 2019 , inexact projections are considered onto two possible sets; the set of the solution of mixed equations and inequalities and a certain smooth manifold given by the image under a nonlinear map of an open set containing the iterates. Inexact projections are also considered in Luke 2013 where the author proposes a theoretical inexactness criterion based on normal cones. We also highlight that both Drusvyatskiy and Lewis 2019 and Luke 2013 consider easy to project onto the rank level set since the projection of a matrix Z is given by its truncated SVD. Our point of view is different, as the computation of the SVD is expensive and inherently inexact, and differently from Luke 2013 , we provide inexactness conditions and corresponding stopping criteria for the inner Krylov solver that can be implemented without any additional cost, allowing for the reduction of computational times. Such criteria are inspired by the works Bonettini et al. 2020 ; Bonettini et al. 2021 ; Bonettini et al. 2023 , where implementable inexactness conditions for computing proximal maps are considered in the context of inexact forward–backward algorithms. Unlike these previous works, we cannot rely on the convexity of the sets involved in problem ( 1.1 ); for that reason, our definition of inexact projection will be slightly more restrictive.

Read the complete text