PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Rank Matrix Completion: A Contemporary Survey

Luong Trung Nguyen, Junhan Kim, Byonghyo Shim

arXiv:1907.11705v1cs.DScs.ITmath.OC

TL;DR

LRMC research is difficult to navigate because many studies are highly theoretical or propose new techniques. This paper surveys LRMC by structuring scattered results, classifying techniques, discussing design considerations, and reviewing performance and complexity.

  • Problem

    Existing LRMC studies make essential knowledge difficult to grasp because many are highly theoretical or propose new techniques.

  • Method

    The paper provides a contemporary survey that organizes scattered LRMC results, classifies techniques into two categories, and discusses recovery properties, special structures, CNN-based methods, performance, and complexity.

  • Results

    The survey presents a structured and accessible account of LRMC techniques, their recovery considerations, and their performance and computational complexity.

  • Takeaways & Limitations

    The paper aims to provide researchers, practitioners, and non-experts with a guide to understanding LRMC's potentials and limitations.

  • Takeaways & Limitations

    Most LRMC techniques assume that the original low-rank matrix is random.

Abstract

from arXiv · show

As a paradigm to recover unknown entries of a matrix from partial observations, low-rank matrix completion (LRMC) has generated a great deal of interest. Over the years, there have been lots of works on this topic but it might not be easy to grasp the essential knowledge from these studies. This is mainly because many of these works are highly theoretical or a proposal of new LRMC technique. In this paper, we give a contemporary survey on LRMC. In order to provide better view, insight, and understanding of potentials and limitations of LRMC, we present early scattered results in a structured and accessible way. Specifically, we classify the state-of-the-art LRMC techniques into two main categories and then explain each category in detail. We next discuss issues to be considered when one considers using LRMC techniques. These include intrinsic properties required for the matrix recovery and how to exploit a special structure in LRMC design. We also discuss the convolutional neural network (CNN) based LRMC algorithms exploiting the graph structure of a low-rank matrix. Further, we present the recovery performance and the computational complexity of the state-of-the-art LRMC techniques. Our hope is that this survey article will serve as a useful guide for practitioners and non-experts to catch the gist of LRMC.

I. INTRODUCTION

Low-rank matrix completion recovers missing matrix entries by exploiting low-dimensional structure, addressing ill-posed partial observation problems across recommendation, localization, phase retrieval, and imaging. This survey organizes LRMC methods and discusses their applications, design issues, performance, complexity, and practical selection.

  • Applications: Recommendation systems model user–item ratings as low-rank because users with similar interests tend to provide similar ratings.The survey describes sparse ratings as a setting where LRMC estimates users’ interests.
  • Motivation: Without a rank restriction, partial matrix recovery is ill-posed because infinitely many matrices can agree with the observed entries.The low-rank constraint supplies relationships among entries that make recovery possible.
  • Applications: LRMC is applied to phase retrieval by converting magnitude measurements into linear measurements of a rank-1 positive semidefinite matrix.The lifted matrix is M = mmH, and quadratic Fourier magnitudes become linear measurements of M.
  • Applications: In IoT localization, sparse pairwise distance measurements are used to reconstruct Euclidean distance matrices and infer sensor locations.Missing distances arise from power outages, limited radio range, and vehicle dead zones.
  • Survey scope: The survey structures scattered LRMC results into two technique categories and examines intrinsic recovery properties, special matrix structures, performance, and computational complexity.It also introduces CNN-based LRMC algorithms that exploit graph structure.
  • Survey scope: The paper compares state-of-the-art methods through numerical simulations to clarify recovery quality, running-time complexity, and algorithm-selection trade-offs.The survey aims to help researchers and practitioners determine suitable techniques for given problem setups.

II. BASICS OF LOW-RANK MATRIX COMPLETION

LRMC recovers a low-rank matrix from partial observations by solving a rank-minimization problem, but direct combinatorial search is infeasible because of exponential complexity. The survey organizes LRMC algorithms into methods that do or do not exploit rank information.

  • LRMC seeks to recover a desired low-rank matrix from its observed entries by solving a rank-minimization problem.The observations are represented by an index set or sampling operator.
  • A naive rank-minimization solver uses combinatorial search over successive rank assumptions and corresponding linear-dependence systems.For rank one, columns are assumed linearly dependent; if unsolved, the procedure advances to rank two and beyond.
  • Exponential complexity in problem size makes combinatorial search infeasible for most practical scenarios.
  • The survey presents LRMC as a cost-effective alternative and organizes existing techniques to support comparison across different problem setups.
  • LRMC algorithms are classified into methods that do not use rank information and methods that exploit rank information.The survey discusses both categories in depth and outlines them in Fig. 3.

A. LRMC Algorithms Without the Rank Information

Without rank information, LRMC methods replace rank minimization with convex or iterative surrogates. The survey covers NNM, SVT, and IRLS, emphasizing recovery guarantees and computational trade-offs.

  • Nuclear Norm Minimization: Nuclear norm minimization uses the nuclear norm as a convex surrogate for rank(X), and it is the convex envelope of rank on a bounded spectral-norm set.This relaxation converts the combinatorial rank problem into convex optimization.
  • Nuclear Norm Minimization: Under suitably random observations and conditions involving the matrix coherence, the original matrix is the unique NNM solution with overwhelming probability.The guarantee applies to a rank-r matrix when the number and pattern of observed entries satisfy the stated conditions.
  • Nuclear Norm Minimization: SDP implementations of NNM have computational complexity O(n^3), while an equivalent nonconvex formulation reduces primal variables from n1n2 to r(n1 + n2).The reduced formulation exploits r ≤ min(n1, n2).
  • Singular Value Thresholding: SVT mitigates NNM’s computational burden through iterative singular-value thresholding, requiring truncated SVD and elementary matrix operations per iteration.Its solution converges to the NNM solution as τ →∞.
  • Singular Value Thresholding: When thresholded singular values approach the original rank, SVT has complexity O(rn1n2) and requires O(1/ǫ) iterations for an ǫ-approximation.A large τ is suggested in practice for faster convergence.
  • Iteratively Reweighted Least Squares Minimization: IRLS provides another computationally efficient NNM solver with per-iteration complexity O(rn1n2), using iteratively updated weighted least-squares subproblems.Perturbing singular values helps avoid ill-behavior when some singular values approach zero.

B. LRMC Algorithms Using Rank Information

When rank information is available, LRMC can impose an explicit rank constraint and minimize observed-entry reconstruction error. These methods are well-posed for noisy settings and can use gradient-based optimization with global convergence under suitable conditions.

  • Rank-Constrained Formulation: Known or bounded rank enables Frobenius norm minimization subject to rank(X) ≤r.The formulation is motivated by applications where matrix rank is known in advance, such as Euclidean distance matrices.
  • Frobenius Norm Minimization: Frobenius norm minimization is well-posed in noisy scenarios and has a differentiable cost function suitable for gradient descent, conjugate gradient, Newton, and manifold optimization.Approximate rank information, such as an upper bound, can also be incorporated.
  • Gradient-Based Algorithms: Under suitable sampling-ratio and coherence conditions, gradient-based FNM algorithms globally converge to the original matrix with high probability.The relevant conditions involve p = |Ω|/(n1n2) and the largest coherence µ0.
  • Algorithm Families: FNM-based techniques include greedy methods, alternating projections, and optimization over Riemannian manifolds.These methods address the rank-constrained formulation through different optimization structures.

1) Greedy Techniques:

Rank-informed LRMC methods include greedy, alternating minimization, and Riemannian optimization approaches. They exploit low-rank structure to reduce computation, but alternating methods may converge to local solutions.

  • Greedy Techniques: ADMiRA extends CoSaMP by adding 2r rank-one atoms from the residual and pruning the enlarged set to r atoms.The residual is formed from observed entries, and leading singular components identify candidate atoms.
  • Greedy Techniques: ADMiRA has per-iteration complexity O(rn1n2) and requires O(1/ǫ) iterations to achieve an ǫ-approximation.Its dominant operations are least-squares computation and truncated SVD.
  • Alternating Minimization Techniques: Alternating minimization factorizes M as XY and alternately updates the two factors to minimize sampled reconstruction residual.Power factorization, ASD, and LMaFit are examples of this family.
  • Alternating Minimization Techniques: Alternating methods avoid SVD and invert smaller matrices, yielding complexity O(r|Ω| + r2n1 + r2n2) and O(log(1/ǫ)) iterations for ASD and LMaFit.They are described as simple to implement and memory-efficient when r is small.
  • Alternating Minimization Techniques: A major drawback of alternating minimization is possible convergence to a local solution.This limitation contrasts with the globally optimal solutions associated with convex optimization.
  • Optimization over Smooth Riemannian Manifold: Riemannian optimization treats the fixed-rank feasible set as a smooth manifold, enabling gradient, Hessian, exponential-map, and parallel-translation methods.The formulation converts the rank-constrained problem into optimization over a structured non-vector space.
  • Optimization over Smooth Riemannian Manifold: Riemannian LRMC methods offer simple implementation and fast convergence, with per-iteration complexity O(r|Ω|+r2n1+r2n2).Their stated computational profile matches that of ASD and LMaFit.

4) Truncated NNM:

Truncated NNM incorporates known rank information by penalizing only the smallest singular values, enabling iterative optimization with lower dominant-operation complexity than NNM when the rank is small.

  • Truncated NNM is presented as a variation of NNM, with its algorithm summarized in Table IV and alternative DC-based optimization also available.
  • Truncated NNM uses the rank information r and considers only the n−r smallest singular values rather than all singular values.
  • The method iteratively updates X_i, starting from X_0 = P_Ω(M), using the singular vectors of X_{i−1}.
  • The approach can incorporate the desired matrix rank and supports gradient-based methods including ADMM, ADMMAP, and APGL.
  • O(rn_1n_2) is the dominant truncated-SVD operation complexity, much smaller than NNM when r ≪ min(n_1,n_2).

III. ISSUES TO BE CONSIDERED WHEN USING LRMC TECHNIQUES

Successful LRMC requires sufficiently many observations and suitable distribution of information: degrees of freedom provide a lower bound, while observation sparsity and matrix incoherence affect recoverability.

  • LRMC recovery depends on sparsity of observed entries and incoherence of the matrix.
  • A rank-r square matrix has 2nr−r^2 degrees of freedom, while an n_1×n_2 matrix has (n_1+n_2)r−r^2.
  • When r is small, the matrix has O(n) essential information, but observing fewer than its degrees of freedom makes recovery impossible.
  • With observations arranged to equal the degrees of freedom, recovery identifies linear coefficients from r equations and then reconstructs unknown entries column by column.
  • The illustrated reconstruction has O(r^3) coefficient-estimation cost and O(rn^2) total recovery complexity.
  • Degrees-of-freedom-sized sampling is necessary but generally insufficient, because missing strategically placed entries can prevent recovery.

2) Coherence:

Coherence measures how concentrated a matrix’s singular-vector subspaces are in coordinate directions; high concentration can make recovery require many observations or become impossible.

  • A rank-one matrix with only four top-left nonzero entries cannot be recovered even when 99.99% of entries are observed, because information-bearing entries are missing.
  • In contrast, the spread-out matrix M2 can be recovered from 2n−1 observed entries, equal to its degrees of freedom.
  • The left singular vectors determine vertical row concentration, while the right singular vectors determine horizontal column concentration.
  • If a coordinate basis vector lies in the singular-vector span while others are orthogonal, nonzero matrix entries can be confined to one row, preventing inference from other rows.
  • Coherence quantifies matrix concentration, and both μ(U) and μ(V) assess concentration along row and column directions.
  • Coherence is maximized by concentration in a row or column and minimized when nonzero entries are widely spread.

3. In this case, as illustrated in Fig. III-A2(b),

The survey discusses exploiting special matrix structure in LRMC, including positive semidefinite, Euclidean-distance, and recommendation matrices, and describes rank-aware optimization for PSD completion.

  • The survey examines LRMC for positive semidefinite, Euclidean distance, and recommendation matrices to exploit special structure.
  • 1) Low-Rank PSD Matrix Completion: A low-rank PSD matrix is symmetric and satisfies z^TMz ≥ 0 for every vector z.
  • 1) Low-Rank PSD Matrix Completion: The relaxed PSD completion problem uses the nuclear norm and can be solved with semidefinite-programming solvers.
  • 1) Low-Rank PSD Matrix Completion: When rank(M)=k, PSD structure permits the factorization M=ZZ^T with Z∈R^{n×k}, simplifying the completion problem.
  • 1) Low-Rank PSD Matrix Completion: Under suitable coherence and observation-count conditions, gradient-based algorithms for the reformulated problem have global convergence.
  • 2) Euclidean Distance Matrix Completion: Euclidean distance matrix completion arises in localization applications such as sensor-node localization in IoT networks.

2. It is obvious

The survey describes CNN-based LRMC as learning graph-based mappings for low-rank factors, while highlighting graph convolution design and computational trade-offs. It also introduces atomic norm minimization and manifold-based optimization as additional LRMC approaches.

  • Optimization-based LRMC: Gradient-based optimization can solve the smooth-manifold formulation of LRMC, while atomic-norm formulations can be solved using semidefinite-programming or greedy methods.The survey identifies steepest descent, Newton, and conjugate-gradient methods for the manifold formulation and SDPT3 for the SDP formulation.
  • Convolutional Neural Network Based Matrix Completion: CNN-based LRMC represents a low-rank matrix as a graph and applies CNNs to recover it.The approach is especially useful when the matrix has an associated graph structure, such as user similarities in recommendation data.
  • Graphical Model of a Low-Rank Matrix: Column and row graphs connect users and products according to correlations exceeding a threshold, producing adjacency matrices for graph processing.The column graph represents users, while the row graph represents products.
  • CNN-based LRMC: CNN-based LRMC learns nonlinear mappings from row and column graph vertices to the factors U and V, updating them by minimizing a graph-regularized loss.The procedure initializes U and V randomly, performs graph convolutions, updates the factors, and backpropagates filter parameters until convergence.
  • CNN-based LRMC: Graph convolution is required because row and column graphs do not lie on regular image-like lattices, so classical CNNs cannot be directly applied.Fourier-domain graph convolutions, Laplacian eigendecomposition, and polynomial filters are presented as possible solutions.
  • Atomic Norm Minimization: Atomic norm minimization generalizes rank-one and basis-element representations by representing arbitrary data with a small number of atoms.Its atomic norm generalizes both the ℓ1-norm and the nuclear norm in the space of sinusoidal signals.

IV. NUMERICAL EVALUATION

The numerical evaluation compares LRMC recovery, runtime, scalability, noisy-data robustness, and image restoration. NNM methods generally recover more reliably, whereas FNM methods are often faster and can perform well under noise.

  • Recovery performance: LRMC recovery is poor with few observed entries and large rank, while NNM algorithms generally outperform FNM algorithms.NNM with the SDPT3 solver performs best in the phase-transition comparison, consistent with its global convex optimum.
  • Computational efficiency: Convex LRMC algorithms have relatively high running-time complexity, whereas SVT, IRLS-M, ASD, ADMiRA, and LRGeomCG reconstruct 1000×1000 matrices in under a minute.SDPT3 requires more than five minutes in the reported comparison.
  • Computational efficiency: LMaFit reconstructs a 1000×1000 rank-5 matrix in about one second, illustrating the speed advantage of alternating-projection methods.The evaluation identifies further runtime reduction through alternating projection-based algorithms.
  • Algorithm selection: FNM-based methods are recommended when exact recovery is unnecessary because they offer faster computation, while NNM methods are more reliable for recovery.The evaluation frames algorithm selection as a trade-off between running time and recovery performance.
  • Noisy recovery: At SNR = 20 dB, TNNR-ADMM performs comparably to NNM algorithms because its FNM-based cost function is robust to noise.At SNR = 50 dB, NNM with SDPT3 has the best MSE performance.
  • Image recovery: For impulse-noise image recovery, all methods achieve at least 52 dB pSNR at ρ = 0.3, while NNM with SDPT3, SVT, and IRLS-M reach pSNR ≥57 dB at ρ = 0.7.The images are 256×256 grayscale images corrupted by salt-and-pepper noise.

V. CONCLUDING REMARKS

The survey organizes LRMC methods by whether rank is known, reviews structural assumptions and CNN-based approaches, and compares accuracy with computational cost. Its conclusions emphasize choosing methods according to recovery requirements, scale, and operating conditions.

  • Survey scope: The survey classifies state-of-the-art LRMC methods into NNM-based methods for unknown rank and FNM-based methods for known rank.It discusses SDP-based NNM, SVT, truncated NNM, greedy methods, alternating projections, and Riemannian-manifold optimization.
  • Design considerations: The paper examines sparsity, incoherence, and special matrix structures such as PSD, Euclidean-distance, and graph structures in LRMC design.It also compares recovery performance, running time, and computational complexity across techniques.
  • Algorithm choice: SDP-based NNM is suggested when recovered-matrix accuracy is critical, whereas LMaFit and LRGeomCG suit large-scale problems because their complexity scales as O(r|Ω|).The survey contrasts this with SDP-based NNM complexity of O(n^3).
  • Algorithm choice: FNM algorithms such as LMaFit and ADMiRA converge faster, while NNM algorithms are more reliable, creating a trade-off between runtime and recovery performance.The recommended choice depends on the problem setup and operating conditions.
  • Future directions: Large-scale and real-time applications motivate LRMC algorithms with good recovery guarantees, linear scaling, low complexity, and short running time.The survey specifically mentions IoT localization and massive MIMO as examples.
  • Future directions: Existing LRMC techniques often assume randomly generated matrices, leaving a need for practical algorithms for matrices whose entries come from discrete sets.Recommendation ratings on a 1∼5 scale are given as an example, and the survey notes that no well-known practical guideline currently exists.
  • Future directions: CNN-based LRMC treats observed entries as labeled training data, but defining an accurate graph model can be difficult because multiple edge criteria are possible.The survey identifies GAN-based methods as a possible direction for addressing this issue.

APPENDIX A PROOF OF THE SDP FORM OF NNM

The appendices derive an SDP representation of nuclear norm minimization and state recovery guarantees under sampling and coherence conditions. They connect exact recovery to a dual certificate and injective sampling on the tangent space.

  • APPENDIX A PROOF OF THE SDP FORM OF NNM: The NNM problem is converted into epigraph form before transforming its constraints into the standard SDP form.The nuclear-norm constraint is represented using symmetric auxiliary matrices and a positive-semidefinite block matrix.
  • APPENDIX A PROOF OF THE SDP FORM OF NNM: The sampling equality constraint is expressed through linear inner-product constraints ⟨Y, A_k⟩ = b_k for the observed entries.The appendix illustrates the construction using a small example with a specified observed-index set.
  • APPENDIX A PROOF OF THE SDP FORM OF NNM: The appendix concludes that the reformulated SDP is equivalent to the original NNM problem.The compact expression is identified as the desired result of the conversion.
  • APPENDIX B PERFORMANCE GUARANTEE OF NNM: Exact recovery by NNM depends on the observation model and the intrinsic coherence of the target matrix under uniform sampling.The coherence parameters describe the column and row spaces of the matrix.
  • APPENDIX B PERFORMANCE GUARANTEE OF NNM: A dual certificate Y = UV^T + W with W ∈ T⊥ and ||W|| < 1, together with injective sampling on T, ensures uniqueness of the NNM solution.These conditions characterize the tangent-space requirements used in the uniqueness argument.
  • APPENDIX B PERFORMANCE GUARANTEE OF NNM: Theorem 4 states that, under its sampling and coherence conditions, the target matrix is the unique NNM solution with probability at least 1 − βn^-γ.The theorem assumes n1 = n2 = n and γ > 2.
Loading 1907.11705v1…