Source-linked AI summary
Low-rank matrix recovery via iteratively reweighted least squares minimization
Massimo Fornasier, Holger Rauhut, Rachel Ward
TL;DR
The paper addresses scalable low-rank matrix recovery when rank minimization is computationally hard and standard semidefinite programming is limited in matrix size. It develops an efficient IRLS method with recovery guarantees under a matrix null space property and competitive matrix-completion experiments.
Problem
Rank minimization is NP-hard, while standard semidefinite programming tools efficiently handle nuclear-norm problems only up to approximately 100 × 100 matrices.
Method
The paper analyzes a matrix IRLS algorithm that combines nuclear-norm and approximate low-rank promotion, using partial singular value decompositions and least-squares updates.
Results
Under a suitable matrix null space property, IRLS-M iteratively approximates arbitrary matrices within a factor of their best k-rank approximation error in nuclear norm.
Takeaways & Limitations
The implementation can exploit the Woodbury identity and has complexity advantages for separable measurement operators, while experiments find it competitive for matrix completion.
Takeaways & Limitations
Matrix completion violates RIP, and the paper postpones the more involved theoretical analysis of IRLS-M for that setting.
Abstract
from arXiv · showhide
We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal nuclear norm and an approximatively low-rank solution. Under the assumption that the linear measurements fulfill a suitable generalization of the Null Space Property known in the context of compressed sensing, the algorithm is guaranteed to recover iteratively any matrix with an error of the order of the best k-rank approximation. In certain relevant cases, for instance for the matrix completion problem, our version of this algorithm can take advantage of the Woodbury matrix identity, which allows to expedite the solution of the least squares problems required at each iteration. We present numerical experiments that confirm the robustness of the algorithm for the solution of matrix completion problems, and demonstrate its competitiveness with respect to other techniques proposed recently in the literature.
1. Introduction.
Affine rank minimization seeks minimum-rank matrices satisfying underdetermined measurements, but its computational hardness motivates nuclear-norm and iteratively reweighted least-squares alternatives for scalable low-rank recovery.
- NP-hardness makes tractable alternatives desirable, motivating nuclear norm minimization as a convex proxy for rank minimization.The nuclear norm is the ℓ1-norm of singular values and the smallest convex envelope of rank.
- Standard semidefinite programming is efficient only for matrices up to approximately 100 × 100, motivating specialized algorithms.
- The proposed matrix IRLS variant uses partial singular value decompositions and usually small least-squares problems at each iteration.Both computational tasks are described as efficiently performable.
- The analysis uses a matrix extension of the null space property, while numerical experiments assess competitiveness in matrix completion.The paper connects this property to ℓ1-minimization and compressed sensing.
- Low-rank recovery supports applications including collaborative filtering, quantum state tomography, signal processing, image processing, and matrix completion.
1. RIP measurement maps.
The paper characterizes measurement conditions for nuclear-norm recovery, emphasizing RIP-based guarantees for random maps and the failure of RIP in matrix completion without incoherence assumptions.
- The rank restricted isometry property is formulated through constants δ_k associated with a linear measurement map.
- Nuclear norm minimization recovers rank-at-most-k matrices when δ_5k is sufficiently small, with the paper improving this condition to δ_4k.
- Gaussian and subgaussian measurement maps are known to satisfy the restricted isometry property under suitable measurement conditions.
- For Gaussian measurements, the required bound matches the degrees of freedom k(n + p − k) up to a possible constant, making it optimal.
- Structured random partial Fourier measurements satisfy RIP with high probability when m ≥ Ck max{n, p} log2(max{n, p}).The cited discussion calls this bound optimal up to possibly the exponent 2 on the logarithmic term.
- Matrix completion violates RIP because rank-one matrices can lie in the measurement kernel, so recovery requires incoherence conditions on singular vectors.Without such conditions, localized low-rank null-space matrices cannot be recovered by any method.
2. Matrix completion.
For structured random partial Fourier measurements, the paper gives a near-optimal measurement scaling for the restricted isometry property.
- m ≥ Ck max{n, p} log2(max{n, p}) measurements suffice for RIP with high probability for randomized partial Fourier maps.The bound is described as optimal up to possibly the exponent 2 on the logarithmic term.
2. Notation and Preliminaries.
The section formulates low-rank matrix recovery through linear measurements and develops IRLS-M as a stabilized, iteratively reweighted least-squares approach. Under restricted-isometry-type assumptions, the method has recovery guarantees, while matrix completion remains outside the theory.
- Affine rank minimization seeks a minimum-rank matrix satisfying an underdetermined linear system, with matrix completion as an important special case.
- ε-stabilization raises singular values below ε, keeping weight computations well-conditioned while permitting εℓ→0 for convergence toward a k-rank solution.The stabilization preserves approximation by a best k-rank matrix when the input is approximately low-rank.
- With suitable restricted isometry constants, IRLS-M converges to a k-rank solution and robustly approximates arbitrary matrices within a factor of their best k-rank nuclear-norm error.The stated guarantee uses γ = 1/n and conditions involving δ3K and δ4K.
- For matrix completion, restricted isometry fails, so the proposition does not apply; nevertheless, numerical experiments evaluate IRLS-M against FPCA and OptSpace.
3. Numerical Experiments.
The experiments compare IRLS-M with FPCA and OptSpace on synthetic low-rank matrices, noisy measurements, and grayscale-image completion. Results indicate competitive accuracy, advantages over OptSpace, and improved accuracy over FPCA at sufficiently many measurements, with a speed trade-off.
- Synthetic matrices: Synthetic experiments compare IRLS-M, FPCA, and OptSpace on randomly generated rank-10 and rank-30 matrices.The rank-10 experiments use 500 × 500 matrices and average relative error and reconstruction time over 50 trials.
- Noisy recovery: Noisy synthetic experiments repeat the rank-10 and rank-30 settings with observations corrupted by additive noise .1Nij.
- Image reconstruction: Image experiments use randomly sampled partial pixels and compare reconstructions after thresholding negative pixel values to zero.The images provide nonrandom matrices whose singular values are sharply decaying and are well-approximated by low-rank matrices.
- Accuracy: IRLS-M outperforms OptSpace on reconstructing low-rank and approximately low-rank matrices with rapidly decaying singular values.
- Accuracy: IRLS-M is competitive with FPCA in accuracy and becomes more accurate than FPCA once the number of measurements is sufficiently high.
- Speed and scope: IRLS-M can be slower than FPCA, while image examples suggest greater accuracy for approximately low-rank matrices with sharply decaying singular values.
- Experimental limitations: All three algorithms are rank-aware, requiring the underlying rank as an input; the image ranks and measurement counts were selected by visual inspection.Cross-validation is identified as a more systematic rank-selection approach.
4. Computational Considerations.
The implementation reduces the computational cost of IRLS-M updates by exploiting low-rank structure, separable matrix-completion operators, parallel column updates, and the Woodbury identity.
- Updating W: Only the first r singular vectors of W ℓ are needed for the weight update, rather than all n singular vectors.Here r is the largest integer satisfying σr > εℓ/γ.
- Updating W: With γ = 1, W ℓ decomposes into a low-rank matrix plus a perturbation of the identity, and r is on the order of K.This structure avoids computing the full singular-vector decomposition in practice.
- Updating X: In matrix completion, the operator S acts columnwise, so the weighted least-squares update separates into independent problems for each column.Each column solves a constrained minimum-norm problem involving Si and W.
- Updating X: The independent column updates can be parallelized, further reducing the time required to compute the matrix update.The relevant linear systems involve the per-column operators Si.
- Woodbury acceleration: For matrix completion, Si is a subset of rows of the identity, allowing the Woodbury reduction to use Ui formed from corresponding rows of U.The resulting system is much smaller when r is far below the number of measurements in a column.
5. Variational Interpretation.
The paper reformulates low-rank matrix recovery as alternating minimization over a matrix variable and a positive-definite weight matrix, yielding explicit update characterizations and solutions.
- Variational formulation: Low-rank matrix recovery is reformulated as alternating minimization of a matrix functional over X and a positive-definite weight matrix W.The IRLS-M iterations are presented through successive updates of these two variables.
- Algorithm: IRLS-M initializes W 0 as the identity, sets ε0 = 1 with K ≥ k and γ > 0, then recursively generates matrix and weight updates.The sequence terminates when εℓ = 0; otherwise it may be infinite.
- Updating X: For fixed W, the matrix update minimizes the functional subject to S(X) = M and satisfies the weighted orthogonality condition S∗(λ) = W X̄.The explicit solution uses W−1 and the inverse of S ◦ W−1 ◦ S∗.
- Updating X: The optimality derivation expands the trace objective along perturbations H in ker S and reduces stationarity to vanishing real inner products.This establishes the stated weighted orthogonality condition for feasible perturbations.
- Updating W: For fixed X, the weight update minimizes the functional over positive-definite W bounded above by ε−1I.The analysis relaxes this to a positive-semidefinite convex constraint and uses a Lagrangian and KKT conditions.
- Updating W: The weight minimizer is characterized through duality and, for X = UΣV∗, has the explicit form W̄ = UΣ−1_εU∗.The dual solution also minimizes the original constrained problem because it lies in the original feasible set.
6. Analysis of the Algorithm.
The analysis establishes convergence and recovery guarantees for IRLS-M under rank-based null space conditions, while also identifying computational benefits and theoretical limitations of the update rule.
- Null space property: The rank null space property characterizes when nuclear norm minimization uniquely recovers every matrix of rank at most k.Theorem 6.3 states the equivalence between this recovery guarantee and the RNSP of order k.
- Null space property: The strong rank null space property yields stable recovery, with error controlled by the best k-rank approximation error in the nuclear norm.The analysis introduces ρ_k(X)_* as this approximation error and derives an inverse triangle inequality under the SRNSP.
- Analysis of the algorithm when S satisfies the null space property: Under suitable SRNSP and parameter conditions, IRLS-M converges to a nuclear norm minimizer or approximates arbitrary feasible matrices at the best k-rank error scale.The guarantee applies for k < K − 2η/(1−η), with η < 1 − 2/K^2.
- Discussion of related work: The update rule introduces additional convergence-proof difficulty because it uses constrained rather than unconstrained minimization in the weight variable.The same choice is motivated by a significant complexity reduction when the measurement operator acts columnwise, with Woodbury-based inversion providing further savings.
- Discussion of related work: Matrix completion does not satisfy the null space property, so the theoretical guarantee does not apply there, although the algorithm can still perform well numerically.The paper separately reports strong empirical performance for matrix completion and discusses improved computational complexity from its update rule.
7. Appendix.
The appendix develops singular-value inequalities and characterizes unitarily invariant matrix functions through absolutely symmetric functions of singular values. It also records a differentiability criterion and acknowledges contributors and funding support.
- Singular-value estimates: Weyl’s estimate bounds each singular-value difference by the Frobenius distance between two matrices.The bound is |σ_i(X) − σ_i(Y)| ≤ ∥X − Y∥_F for every i.
- Singular-value estimates: For any J > j, (J − j)σ_J(X) is bounded by the nuclear distance ∥X − Y∥_* plus the tail error ∥Y − Y[j]∥_* .This relates a singular value of X to its approximation by Y and the best j-rank truncation of Y.
- Unitarily invariant functions: Absolutely symmetric functions of singular values characterize unitarily invariant functions on matrices.For n ≤ p, F is unitarily invariant exactly when F(X) = f(σ(X)) for an absolutely symmetric f.
- Unitarily invariant functions: For absolutely symmetric convex f, the matrix function f ◦ σ is convex, and differentiability of f ◦ σ at X is equivalent to differentiability of f at σ(X).The appendix also states that the corresponding derivative formula follows in this case.
- Acknowledgments: The appendix closes with acknowledgments to Ingrid Daubechies and Maryam Fazel and notes financial support for Massimo Fornasier.It also identifies contributions to named institutional projects.