Rank Selection Strategies for AP Methods Applied to the Affine Rank Minimization Problem
Please login to view abstract download link
Consider the problem of finding a matrix M with minimum rank satisfying an affine condition of the form A(M) = b, with A affine map. This is known as Affine Rank Minimization Problem and appears in many applications. An example is Matrix Completion in Sparse Image Reconstruction. In this talk we reformulate it as a feasibility problem, that is, find, if there exists, a matrix in the intersection of two suitable sets: an affine set and the rank level set. The feasibility problem can be solved using Alternating Projection Method (APM), that consists in projecting back and forth onto the two sets until convergence and it was introduced by Von Neumann in 1951. The method is guaranteed to converge only in the convex case, while in the non-convex case only local convergence results hold. Attouch el al. proposed a regularized version of APM (RAPM) and proved its global convergence to a stationary point. Projecting onto the rank level set requires computing a truncated SVD, which is costly even with iterative methods like PROPACK. To reduce this cost, Bellavia ed al. proposed iRAPM, an inexact variant of RAPM that allows early stopping for SVD computation based on suitable inexactness criteria. iRAPM has been shown to preserve the global convergence of RAPM, without impact on performance in practice. AP methods require knowing the rank of the matrix M in advance. This is a limitation in applications where usually only estimates of the rank are available. Then, it becomes crucial to implement strategies to automatically select the rank. We present the most common strategies and discuss their characteristics. Extended experiments will also be shown to compare the effectiveness of strategies applied in different problems raised by applications.
