PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of fixed-point continuation algorithms for matrix rank minimization

Donald Goldfarb, Shiqian Ma

arXiv:0906.3499v4math.OCcs.IT

TL;DR

Matrix rank minimization is NP-hard, so the paper studies tractable nuclear-norm relaxation and fixed-point continuation methods for affinely constrained problems. It analyzes FPCA and related variants, establishes convergence and recoverability properties, proposes rank-selection heuristics, and reports numerical results. FPCA can recover matrices with rank close to the largest rank recoverable from the available samples, while the theory relies on RIP conditions that exclude matrix completion.

  • Problem

    Matrix rank minimization is NP-hard, motivating study of nuclear-norm relaxation and scalable algorithms for affinely constrained problems.

  • Method

    The paper analyzes fixed-point continuation with approximate SVD, its thresholding and shrinkage variants, convergence properties, and heuristics for choosing unknown rank.

  • Results

    FPCA can recover matrices whose rank is very close to rmax, the largest rank recoverable with p samples; the paper also reports numerical results for random and real problems.

  • Takeaways & Limitations

    The algorithms provide practical approaches for matrix rank minimization while connecting fixed-point continuation variants to greedy methods in compressed sensing.

Abstract

from arXiv · show

The matrix rank minimization problem has applications in many fields such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem. By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.

1. Introduction.

The paper studies affinely constrained matrix rank minimization, an NP-hard problem whose nuclear-norm relaxation enables tractable recovery under suitable measurement conditions. It analyzes fixed-point continuation methods and variants, including their convergence, recoverability, rank-selection heuristics, and numerical performance.

  • Applications: The framework covers applications including system identification, optimal control, low-dimensional embedding, and matrix completion.Matrix completion includes recommendation systems and the Netflix problem, where missing ratings are filled using a presumed low-rank structure.
  • Problem and relaxation: Matrix rank minimization is NP-hard, motivating replacement of rank by the nuclear norm, its convex envelope on the spectral-norm unit ball.The nuclear norm equals the sum of the nonzero singular values.
  • Convex recovery: Under random measurements with p ≥ Cr(m + n) log(mn), most m × n rank-r matrices can be recovered by solving the nuclear-norm relaxation.The recovery statement holds with very high probability for matrices of rank r.
  • Algorithms and contributions: FPCA combines approximate SVD with fixed-point continuation and can recover matrices whose rank is close to rmax, the largest rank recoverable with p samples.The paper studies FPCA, iterative hard thresholding, matrix-shrinkage variants, and a close variant called FPCAr.
  • Algorithms and contributions: The paper weakens previously required conditions for approximate recovery and reports numerical results on randomly generated and real matrix rank minimization problems.It also proposes heuristics for choosing the rank when the true rank is unknown.

2. Restricted Isometry Property.

The restricted isometry property links matrix rank minimization to its convex relaxation and underpins the paper’s convergence and recoverability analysis. The theory requires RIP, while matrix completion is explicitly identified as a setting where RIP fails.

  • RIP definition and role: The RIP constant δ_r(A) measures how nearly isometric a linear operator is on matrices of rank at most r, with δ_s ≤ δ_t when s ≤ t.The paper uses RIP constants throughout its theoretical development.
  • RIP guarantees: If δ_5r(A) < 0.1, the original rank minimization problem and its nuclear-norm relaxation have the same optimal solution.This is stated as a theorem attributed to Recht, Fazel, and Parrilo.
  • RIP guarantees: For nearly isometric random maps, p ≥ c0r(m + n) log(mn) yields δ_r(A) ≤ δ with probability at least 1 − exp(−c1p).The constants c0 and c1 depend only on δ.
  • Assumptions and scope: The matrix-completion operator does not satisfy the RIP, so the paper’s RIP-based theory does not directly cover that problem.A counterexample is cited for the failure of RIP in matrix completion.
  • Assumptions and scope: The convergence proofs for FPCA variants require the measurement operator A to satisfy the RIP.The paper notes that i.i.d. Gaussian measurement matrices provide a nearly isometric random map and reports strong empirical performance in that setting.

3. FPC Revisited.

FPC solves the nuclear-norm relaxation through operator splitting and fixed-point iterations, while FPCA reduces cost by using approximate SVDs. The paper studies thresholding and shrinkage variants and establishes convergence for the fixed-point scheme under a stepsize condition.

  • Operators: The soft shrinkage operator applies threshold ν to singular values, retaining the singular vectors while replacing each singular value by its positive thresholded value.The passage defines the operator using a matrix SVD and a+ = max(a, 0).
  • FPC and FPCA: FPC applies operator splitting to the nuclear-norm problem’s optimality conditions and uses singular-value shrinkage in each fixed-point iteration.The shrinkage operator provides the solution of the proximal subproblem.
  • Convergence: If τ ∈ (0, 2/λ_max(A* A)), the fixed-point sequence converges to an optimal solution of the nuclear-norm problem.The result is stated for the iterations in equation (3.6).
  • FPC and FPCA: FPCA replaces the expensive full SVD with a rank-r approximation, then applies shrinkage and continuation to improve efficiency and recoverability.Exact computation of the best rank-r approximation can remain expensive for large matrices or non-small r.
  • Variants: FPCA combines hard thresholding, soft shrinkage, and continuation; removing selected components yields IHT, IHTMS, and FPCAr variants.The paper studies these variants in later sections, assuming known rank before introducing rank-selection heuristics.

4. Iterative Hard Thresholding.

This section analyzes IHT, an FPCA variant that uses gradient steps followed by hard thresholding of singular values. Under RIP conditions, it provides convergence and recoverability guarantees for exact and approximate low-rank solutions.

  • Algorithm: IHT is obtained from FPCA by fixing the known rank, removing continuation and soft shrinkage, and using unit stepsize.Each iteration takes a gradient step and retains the largest r singular values.
  • Algorithm: IHT applies hard thresholding to singular values, paralleling compressed-sensing IHT while replacing vector thresholding with matrix singular-value thresholding.The matrix and compressed-sensing algorithms differ in the object to which the shrinkage operator is applied.
  • Proof strategy: The convergence proof relies on low-rank subspace projections, best rank-r approximation properties, and RIP-based bounds on projected operators.The analysis tracks residuals across successive SVD subspaces and iterates the resulting contraction inequality.
  • Convergence results: Under a perturbed system b = AXr + e and an RIP assumption, IHT recovers an approximation to a rank-r solution with convergence controlled by α and the perturbation.The theorem assumes Xr has rank r and gives an iteration-dependent recovery estimate.
  • Convergence results: For arbitrary X, IHT targets the best rank-r approximation and its error also reflects unrecoverable energy from components outside rank r.The result assumes an RIP bound and provides an accuracy guarantee after a finite number of iterations.
  • Comparison: The stated theorems improve earlier affine-constraint recovery conditions by requiring a less restrictive RIP bound than prior results.The paper contrasts its condition near 0.3536 with an earlier requirement of 0.04, while noting related independent work obtained different results.

5. Iterative Hard Thresholding with Matrix Shrinkage.

IHTMS augments iterative hard thresholding with matrix shrinkage while retaining rank truncation. The section establishes convergence and recovery bounds for exact-rank and arbitrary matrices under RIP assumptions.

  • Algorithm: IHTMS applies matrix shrinkage together with rank-r truncation at every iteration, producing a fixed-threshold variant of IHT.The operators commute, so shrinkage and rank truncation can be applied in either order.
  • Algorithm: The algorithm is initialized with X0, a shrinkage parameter µ, and the target rank r, then repeats its update procedure over iterations.The supplied algorithm description explicitly lists these initialization quantities.
  • Convergence results: For b = AXr + e, IHTMS has a convergence result for rank-r solutions under an RIP condition, with accuracy after a bounded number of iterations.The theorem states both an iteration-wise approximation guarantee and a finite-iteration accuracy result.
  • Proof strategy: The proof transfers the IHT analysis to the shrinkage setting by using the best rank-r approximation property of the updated matrix.The argument combines the resulting bound with the preceding inequalities.
  • Convergence results: For arbitrary X, IHTMS estimates the best rank-r approximation while accounting for unrecoverable energy and perturbation effects.The corresponding theorem provides an approximation guarantee and a finite-iteration accuracy bound.

6. FPCA with Given Rank r.

FPCAr uses continuation over the shrinkage parameter while fixing the rank and unit stepsize. Under RIP and staged-iteration conditions, the paper proves recovery guarantees for exact-rank and arbitrary matrices.

  • Algorithm: With known rank r and unit stepsize, the FPCA variant applies continuation by decreasing the shrinkage parameter across successive subproblems.The parameter sequence follows µj+1 = max{µjηµ, µ̄}.
  • Convergence results: For an exact rank-r solution, FPCAr has a convergence guarantee under δ3r(A) ≤ α/8 and staged iteration assumptions.The theorem analyzes the output after K1,...,KL iterations at successive parameter values.
  • Algorithm: FPCAr carries the output from one shrinkage subproblem into the next as the initial point for the reduced parameter.The algorithm is presented as FPCA with given rank r.
  • Proof strategy: The proof proceeds stage by stage, applying the fixed-parameter guarantee repeatedly as continuation moves from µj to µj+1.The section derives the final bound by substituting each stage’s estimate into the next.
  • Convergence results: The recovery error becomes very small when the final shrinkage parameter is small and the final stage uses many iterations.This condition is stated directly after the exact-rank convergence result.
  • Convergence results: For arbitrary X, FPCAr targets the best rank-r approximation and provides a corresponding recovery guarantee under the same continuation framework.The result is stated through Theorem 6.2 and its associated approximation and accuracy expressions.

7. Practical Issues.

The algorithms address unknown rank and expensive best rank-r approximation computations through adaptive rank heuristics and approximate SVD. These choices preserve recoverability while reducing computational cost, although the approximate method is less accurate than PROPACK.

  • Adaptive rank selection: The algorithms start with rmax and adapt r using singular-value thresholds, with safeguards that increase r when truncation is too aggressive.The rank is increased after repeated violations of the shrinkage operator's non-expansive property or when the gradient norm grows by more than 10 times.
  • Adaptive rank selection: The gradient-based rank heuristic enables strong recoverability, including recovery of matrices with rank almost rmax from limited measurements.
  • Approximate SVD: Best rank-r approximation is computationally expensive at every iteration, motivating the use of the Monte Carlo LinearTimeSVD method instead of PROPACK.This issue arises in IHT, IHTMS, and FPCA, which require the approximation at each iteration.
  • Approximate SVD: LinearTimeSVD samples and rescales columns, computes an exact SVD of the smaller matrix C⊤C, and returns approximate leading singular values and vectors.The sampling-based approximation targets the best rank-ks approximation while using O(m + n) time for the returned singular-vector computation.
  • Approximate SVD: Larger cs improves the likelihood that the approximate singular values match the largest singular values of A, but increases the cost of the smaller SVD.Experiments found that relatively small cs reduced computational time without significantly degrading accuracy.
  • Approximate SVD: Although PROPACK is more accurate, the algorithms are robust and not very sensitive to approximate-SVD accuracy.The experiments support using the faster approximate method when computational savings are important.

8. Numerical Experiments.

The experiments evaluate rank-minimization algorithms on random and realistic problems, comparing recovery, convergence, rank-selection heuristics, and compressed-video reconstruction.

  • Experimental setup: The study tests six algorithms, with rank-specified variants compared against heuristic rank-selection variants on random and realistic matrix problems.IHTr, IHTMSr, and FPCAr use a specified rank; IHT, IHTMS, and FPCA determine rank heuristically.
  • Randomly created test problems: For m = n = 60 and 20% sampling, the largest rank satisfying FR < 1 is rmax = 6.
  • Randomly created test problems: Ranks up to 5 were recovered for all random matrices with relative error of order 1e-5, whereas SDPT3 recovered all matrices only at ranks 1 and 2.At rank 3, SDPT3 recovered 3 of 10 matrices; at ranks 4 and 5, it recovered none.
  • Randomly created test problems: The log approximation error was approximately linear in iteration number for a rank-2 problem, supporting the predicted convergence behavior in practice.
  • Rank selection: Heuristic rank selection performed similarly to knowing the true rank and recovered low-rank matrices well without prior rank knowledge.
  • Rank selection: Choosing a rank below the true rank prevented recovery, while slightly overestimating it degraded errors and times; heuristic methods remained successful when the chosen rank was too large.With true rank 3, specified-rank methods failed at ranks 1 and 2, and at rank 6 recovered only 4, 1, and 3 of 10 problems, respectively.
  • Video compression: On compressed video, FPCA recovered the matrix with relative errors comparable to the best rank-5 approximation while using 40% as many measurements as pixels.The experiment used a grayscale, cropped sequence of 20 frames represented as an approximately low-rank matrix.

Appendix.

The appendix proves propositions underlying the analysis of fixed-rank matrix recovery. It establishes RIP-based operator bounds and a convex-hull characterization of rank-constrained matrices.

  • RIP-based bounds: RIP places the eigenvalues of PΨA∗APΨ restricted to span(Ψ) in [1 − δr(A), 1 + δr(A)].This spectral interval is used to establish the relevant operator estimate.
  • RIP-based bounds: For X in span(Ψ′), the appendix bounds the cross term by δr(A)∥(I − PΨ)X∥F∥PΨY∥F for every Y.The proof normalizes the two projected components before applying the RIP bound.
  • Convex-set characterization: A matrix X in K is partitioned by singular-value blocks of size at most r, producing matrices in S with rank at most r and unit Frobenius norm.The decomposition shows that X can be expressed as a convex combination of matrices from S, yielding K ⊂ S.
  • Convex-set characterization: The convex-set inclusion is completed by summing the block relations and using λ0 = ∥σ|I0∥2 ≤ ∥X∥F.The argument concludes that X belongs to S and therefore K ⊂ S.
Loading 0906.3499v4…