Speaker
Description
Consider the affine rank minimization problem [6] defined as
\begin{equation}
\begin{aligned}
\min & \quad \text{rank}(X) \
\textrm{s.t.} & \quad \mathcal{C}_\mathcal{A} (X) = b,
\end{aligned}
\tag{1}
\end{equation}
where $X \in \mathbb{R}^{n_1 \times n_2}$ is a matrix, and linear map $\mathcal{C}_\mathcal{A} : \mathbb{R}^{n_1 \times n_2} \rightarrow \mathbb{R}^m$ and vector $b \in \mathbb{R}^m$ are given.
This problem appears in diverse fields including system identification and control, Euclidean embedding, collaborative filtering, and image reconstruction.
Given two sets $A$ and $B$ with $A \cap B \neq \varnothing$, a feasibility problem consists in
\begin{equation}
\textrm{find} \ x \in A \cap B.
\tag{2}
\end{equation}
Problem (1) is a nonconvex optimization problem due to rank function, and it can be reformulated as (2) considering:
\begin{align}
A &= { X \ | \ \mathcal{C}_\mathcal{A} (X) = b } \
B &= { X \ | \ \text{rank}(X) \le r },
\end{align}
where the rank $r$ is known in advance.
In the 50s, the Alternating Projection Method (APM) was proposed by von Neumann [4] for solving (2) when $A,B$ are linear subspaces. It consists in the simple idea of projecting alternately onto $A$ and $B$ until the generated sequence converges to a point in the intersection. Formally, given $y^0 \in B$, we can define APM's iteration as follows:
\begin{equation}
\begin{cases}
x^k &\in P_A (y^{k-1}) \
y^k &\in P_B (x^{k})
\end{cases}
\quad k = 1, \dots
\tag{3}
\end{equation}
where $P_A, P_B$ are projection operators onto $A$ and $B$, respectively.
The method converges when $A,B$ are convex [1]. When one of the sets is nonconvex, APM converges only locally and further hypothesis on the sets and their intersection are required [5]. The difficulty comes from the projection onto the nonconvex set, which usually is unknown in closed form. To overcome this issue, inexact AP methods have been also proposed [2].
Many works in this field of literature, including those cited above, agree in considering the particular case of rank set an ``easy'' problem, despite the nonconvexity of $\mathcal{C}_r$. Indeed, from the Eckart-Young theorem, the projection of a matrix $X$ onto $\mathcal{C}_r$ is the SVD of $X$ truncated to the first $r$ singular values. Then, $P_{\mathcal{C}_r}$ is considered to be known in exact and closed form [2].
From a numerical perspective, however, it is well known that the SVD of a matrix, as well as its truncated version, is computed through iterative procedures that can be computationally expensive, especially when dealing with large matrices and that unavoidably truncation errors that, to the best of our knowledge, have not been considered in previous studies of methods dealing with the rank set, where the projection is assumed to be exact.
Additionally, in a more general setting, methods employing inexact projections adopt criteria that often involve the geometry of the sets without providing a thorough analysis of their implementation and efficiency from a numerical standpoint.
In this work, we introduce the inexact Regularized APM (iRAPM) that accounts for the inaccuracy of the numerical approximation of the truncated SVD and which is based on inexactness criteria that can be efficiently implemented.
Our inexactness criteria rely on a (problem dependent) subprocedure to replace projection onto the ``hard'' set. In the particular case of (2) with the rank set, we show that the procedure can be defined starting from the Lanczos algorithm for truncated SVD. Indeed, we show that the new criteria can be checked using byproduct quantities of the Lanczos method with negligible additional cost.
For our experiments, we used Lanczos implementation in PROPACK by [3] and we tested iRAPM on the Matrix Completion problem. Results show that iRAPM can be faster that classical APM retaining same reconstruction error.
Reference
- Heinz H Bauschke and Jonathan M Borwein. On projection algorithms for solving convex feasibility
problems. SIAM review, 38(3):367–426, 1996. - Dmitriy Drusvyatskiy and Adrian S Lewis. Local linear convergence for inexact alternating pro-
jections on nonconvex sets. Vietnam Journal of Mathematics, 47:669–681, 2019. - Rasmis Munk Larsen. Lanczos bidiagonalization with partial reorthogonalization. Dept. Computer
Science, Aarhus University, Technical report, DAIMI, PB(537), 1998. - John Von Neumann. Functional Operators (AM-22), Volume 2: The Geometry of Orthogonal
Spaces. (AM-22). Princeton University Press, 1950. - D. Noll and A. Rondepierre. On Local Convergence of the Method of Alternating Projections.
Found. Comput. Math., 16:425–455, 2016. - Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of
linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010.
