Low-Rank Matrix Completion: A Contemporary Survey

Introduction

• In recommendation systems, users with similar interests tend to give similar ratings, producing low-rank rating matrices with many missing entries.The introduction also describes Euclidean distance matrices as low rank, with rank at most k + 2 in k-dimensional space [2],,.Source: §I · pp. 2–5
• Low-rank structure can make recovery possible from few observations, whereas recovering a matrix without a rank restriction is ill-posed because infinitely many matrices fit the observed entries.The introduction explains that a low-rank constraint plays a central role in determining unknown entries.Source: §I · pp. 3–4
• 92% of recovered Euclidean distances have error below 0.5 m using 30% of observed distances, illustrating localization with sparse sensor measurements.Euclidean distance matrices for nodes in k-dimensional space have rank at most k + 2,.Source: Figure 2 · p. 5, §I · pp. 5, 7
• Phase retrieval can be recast as recovering a rank-1 positive semidefinite matrix from linear measurements of the signal’s Fourier magnitudes.The introduction identifies X-ray crystallography and quantum mechanics as applications where only Fourier-transform magnitude is measured.Source: §I · pp. 5–7
• Images can be approximated as low-rank matrices and restored from clean pixels; the illustrated reconstructions achieve peak SNR ≥32 dB.The introduction presents this as an alternative to replacing contaminated pixels with interpolated neighbors.Source: Figure 3 · p. 6, §I · p. 8
• Massive MIMO uses hundreds of base-station antennas for capacity gains and requires channel-state information at the transmitter, which can be estimated from users’ pilot feedback,.The introduction describes joint estimation of all users’ channel state from their observations.Source: §I · p. 8

I. INTRODUCTION

• Because theoretical studies and technique proposals make LRMC’s essentials difficult to grasp, the paper organizes scattered results into an accessible contemporary survey.Its stated aim is to help researchers and practitioners understand LRMC’s potential and limitations.Source: §I · p. 9
• The survey groups state-of-the-art LRMC techniques into two classes and explains them to help researchers choose a method for a given problem setup.It also discusses intrinsic recovery properties and how positive-semidefinite, Euclidean-distance, and graph structures can be exploited in algorithm design.Source: §I · pp. 9–10
• The survey compares LRMC techniques’ recovery quality and running-time complexity through simulations to reveal their pros and cons and inform algorithm choice.It concludes with comments on selecting techniques and future research directions.Source: §I · pp. 9–10
• The paper introduces CNN-based LRMC that exploits the graph structure of a low-rank matrix.More broadly, it discusses using special matrix structure in LRMC design.Source: §I · pp. 9–10

• LRMC formulates recovery of the desired low-rank matrix M as rank minimization over observed entries Ω, equivalently expressed using the sampling operator PΩ.Source: §II · p. 11
• A naive combinatorial search tests successive rank assumptions, but its exponential complexity makes it infeasible for most practical scenarios.The procedure starts with rank(M) = 1 and increases the assumed rank if no solution is found.Source: §II · p. 11
• LRMC algorithms are classified as those without rank information and those exploiting rank information.The survey provides an in-depth discussion of both categories.Source: §II · p. 11

Nuclear Norm Minimization (NNM)

• NNM replaces rank minimization, which is NP-hard at scale, with the nuclear norm as a convex surrogate for rank.The nuclear norm is the convex envelope of rank on the unit spectral-norm ball.Source: A. LRMC Algorithms Without the Rank… · p. 12
• With suitably random observations satisfying a coherence-dependent sample bound, NNM uniquely recovers a rank-r matrix with overwhelming probability.The bound depends on the matrix’s largest coherence, µ0.Source: A. LRMC Algorithms Without the Rank… · p. 12
• SDP solvers for NNM have O(n^3) computational complexity, while an equivalent quadratic formulation reduces primal variables from n1n2 to r(n1 + n2).The reduced formulation applies for r ≤ min(n1, n2).Source: A. LRMC Algorithms Without the Rank… · p. 13

Singular Value Thresholding (SVT)

• SVT’s computational complexity is O(rn1n2), and its solution to problem (14) converges to the NNM solution as τ → ∞.Source: A. LRMC Algorithms Without the Rank… · pp. 13, 15

Iteratively Reweighted Least Squares (IRLS) Minimization

• IRLS, recasts NNM as least-squares minimization with iterative updates, costs O(rn1n2) per iteration, and uses singular-value perturbation to avoid near-zero-value ill-behavior.Source: A. LRMC Algorithms Without the Rank… · p. 16

B. LRMC Algorithms Using Rank Information

• When rank information is available, LRMC can be formulated as FNM subject to rank(X) ≤ r; a Euclidean distance matrix in k dimensions has rank at most k + 2.Source: B. LRMC Algorithms Using Rank… · p. 16
• FNM-based LRMC techniques include greedy methods, alternating projections, and optimization over a Riemannian manifold.Source: B. LRMC Algorithms Using Rank… · pp. 16–17
• Because the rank constraint is an inequality, approximate rank information such as an upper bound has also been used.Source: B. LRMC Algorithms Using Rank… · p. 17
• FNM is well-posed in noisy scenarios and has a differentiable cost function that supports gradient-based optimization methods.The listed methods include gradient descent, conjugate gradient, Newton methods, and manifold optimization.Source: B. LRMC Algorithms Using Rank… · p. 17
• Under suitable sampling ratio p and largest coherence μ0, gradient-based FNM algorithms converge globally to M with high probability.The cited guarantee is conditional on the sampling ratio and coherence conditions.Source: B. LRMC Algorithms Using Rank… · p. 17

1) Greedy Techniques:

• ADMiRA, viewed as an extension of CoSaMP,,,, adds 2r leading principal components of residual Ri to Ai−1 and uses pruning to identify atom set AM.Source: 1) Greedy Techniques · p. 18
• O(rn1n2) is ADMiRA’s per-iteration complexity, driven by least squares and truncated SVD operations.The least-squares cost is O(r|Ω|), while truncated SVD costs O(rn1n2).Source: 1) Greedy Techniques · p. 19
• Rank-one matrix pursuit [44], extending orthogonal matching pursuit, selects the atom corresponding to the largest singular value of the residual.Source: 1) Greedy Techniques · p. 19

2) Alternating Minimization Techniques:

• Alternating minimization factorizes M as XY and minimizes the sampled-space residual; power factorization alternates updates, while ASD uses steepest-gradient updates and LMaFit updates X, Y, and Z.The factor matrices have dimensions n1 × r and r × n2, with r ≪ n1, n2.Source: 1) Greedy Techniques · p. 20
• Each alternating-minimization iteration has computational complexity O(r|Ω| + r²n1 + r²n2), much smaller than that of SVT and ADMiRA when r ≪ min(n1, n2).It avoids SVD computation and requires only pseudoinversion of X and Y, of sizes n1 × r and r × n2, respectively.Source: 1) Greedy Techniques · p. 21

3) Optimization over Smooth Riemannian Manifold:

• When rank is known, the feasible set of rank-r matrices is a smooth Riemannian manifold, enabling manifold optimization methods such as gradient, Newton, or conjugate gradient,.The survey notes that this feasible set is not a vector space, so conventional optimization cannot be applied directly.Source: 1) Greedy Techniques · pp. 21–22
• Riemannian optimization-based LRMC offers simple implementation and fast convergence, and unconstrained optimization over a smooth manifold can reconstruct the original matrix [50].The survey also describes optimization over the Grassmann manifold.Source: 1) Greedy Techniques · p. 22

1) Greedy Techniques:

• Each iteration costs O(r|Ω|+r^2n_1+r^2n_2), and achieves an ǫ-approximation solution in O(log(1…) iterations.The supplied iteration bound is truncated after O(log(1, so its full expression cannot be specified.Source: 1) Greedy Techniques · p. 23

4) Truncated NNM:

• Using rank information r, truncated NNM considers only the n − r smallest singular values of the desired matrix [57].Source: 4) Truncated NNM · p. 23
• The iterative method starts from X0 = PΩ(M) and updates Xi using the left and right singular vectors of Xi−1.Source: 4) Truncated NNM · p. 23
• The approach incorporates rank information and supports gradient-based solvers, including ADMM,, ADMMAP [82], and APGL [83].Source: 4) Truncated NNM · pp. 23–24
• Its dominant operation, truncated SVD, has complexity O(rn1n2), much smaller than NNM when r ≪ min(n1, n2).Source: 4) Truncated NNM · p. 24
• A difference-of-convex-functions algorithm is an alternative for solving the truncated NNM problem.Source: 4) Truncated NNM · p. 24

III. ISSUES TO BE CONSIDERED WHEN USING LRMC TECHNIQUES

• The section examines principles enabling low-rank matrix recovery and how special matrix structure can be exploited in algorithm design.Source: §III · p. 24

A. Intrinsic Properties

• LRMC is characterized by sparse observations and matrix incoherence, which requires nonzero entries to be widely spread for efficient recovery.Source: A. Intrinsic Properties · p. 24
• A rank-r n1 × n2 matrix has (n1 + n2)r − r2 degrees of freedom; for fixed small rank, this is O(n), far below the total entries.Source: A. Intrinsic Properties · p. 25
• The DOF is a fundamental lower bound: if fewer than 2nr − r2 entries are observed, no algorithm can recover the square rank-r matrix.Source: A. Intrinsic Properties · pp. 25, 27
• With the first r rows and columns observed, recovery identifies column-combination coefficients from r equations, then fills remaining entries at O(rn2) cost.Source: A. Intrinsic Properties · p. 26
• Observing exactly the DOF is not sufficient in general: a missing entry in an anchor row can prevent recovery of the corresponding column.Source: A. Intrinsic Properties · p. 27
• The survey notes that recent results find the DOF is not much different from the measurement count that ensures recovery [22],.Source: A. Intrinsic Properties · p. 27

2) Coherence:

• For rank O(1), nuclear-norm minimization requires on the order of n^1.2 entries.Source: 2) Coherence · p. 27
• A rank-one matrix M1 cannot be recovered when its four information-bearing entries are missing, even with 99.99% of entries observed, whereas M2 is recoverable from 2n −1 (= DOF) entries in one row and one column.The contrast shows that low rank alone does not ensure recovery when observations miss concentrated information.Source: 2) Coherence · pp. 28–29
• When a standard basis vector lies in the left singular-vector space, nonzeros can be confined to one row, which cannot be inferred without observing that entire row.The analogous concentration may occur in a column; coherence is maximized when nonzeros are concentrated in a row or column and minimized when they are widely spread.Source: 2) Coherence · pp. 29–30
• Coherence quantifies concentration through projections onto the left and right singular-vector spaces, so both µ(U) and µ(V) must be checked.The left and right singular vectors capture concentration in row and column directions, respectively.Source: 2) Coherence · p. 29

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

• The number of measurements needed for recovery is proportional to matrix coherence [22].Equal values of ∥PUei∥2 across standard basis vectors achieve the lower bound in (51).Source: §3 · p. 31

B. Working With Different Types of Low-Rank Matrices

• The survey considers exploiting structure in PSD [54], Euclidean-distance [4], and recommendation matrices [67].It frames these cases as opportunities to improve performance and computational complexity by using the given structure.Source: B. Working With Different Types of… · p. 31
• For low-rank PSD matrices, recovery is formulated as problem (54), then relaxed with the nuclear norm and solved using SDP solvers.The target matrix is symmetric and satisfies z^TMz ≥ 0 for any vector z.Source: B. Working With Different Types of… · pp. 31–32
• When the PSD matrix rank k is known, writing M = ZZT for Z ∈ Rn×k yields the concise formulation (55).The survey notes that (55) is an unconstrained optimization problem with a differentiable cost function.Source: B. Working With Different Types of… · p. 32
• Steepest descent, conjugate gradient, and Newton methods can be applied to (55), with global convergence shown under suitable coherence and observation-count conditions.The stated conditions concern matrix coherence and the number of observed entries |Ω|.Source: B. Working With Different Types of… · p. 32
• Low-rank Euclidean-distance matrix completion arises in localization, including sensor-node localization in IoT networks.For sensor locations in k-dimensional Euclidean space, with k = 2 or k = 3, entries are mij = ∥zi − zj∥2.Source: B. Working With Different Types of… · p. 32

2. It is obvious

• For a Euclidean distance matrix, rank is at most k + 2, and the recovery problem can be solved with gradient-based methods on a smooth Riemannian manifold,,.The listed methods include steepest descent, Newton, and conjugate gradient.Source: §2 · pp. 32–33

3) Convolutional Neural Network Based Matrix Completion

• CNN-based LRMC is particularly useful when a low-rank matrix has a graph model, and it recovers the matrix by applying CNNs to a graph representation,,,,,, [69].A recommendation matrix with a user-similarity graph is one example.Source: §2 · p. 33

Graphical Model of a Low-Rank Matrix

• The method builds row and column graphs by connecting strongly correlated products and users, using a predetermined threshold for column correlations.Rows and columns are vertices in their respective graphs; the row graph is constructed similarly.Source: §2 · p. 33

CNN-based LRMC

• Given M = UV^T, CNNs learn nonlinear mappings from row- and column-graph vertices to rows of U and V, which are initialized randomly and updated to minimize a loss.The mappings are difficult to express explicitly.Source: §2 · p. 34
• Because graph inputs do not lie on regular image lattices, classical CNNs cannot directly operate on them; graph-Fourier approaches include Laplacian eigendecomposition and polynomial filters,, [69], [71].Polynomial filters are proposed to further reduce model complexity.Source: §2 · p. 34

3) Convolutional Neural Network Based Matrix Completion

• The approach has computational cost O(r|Ω|+r2n1+r2n2), much lower than the SVD-based LRMC techniques’ cost O(rn1n2) as long as r ≪ min(n1,n2).Source: §2 · p. 35

CNN-based LRMC

• Upon convergence of the factors to bU and bV, the CNN-based estimate of M is bU bV^T.Filter parameters are updated using backpropagation.Source: §2 · p. 35

4) Atomic Norm Minimization

• Atomic norm minimization generalizes representing a low-rank matrix with a few rank-one terms to representing data with a small number of basis atoms, and its reconstruction problem has an equivalent SDP form [87, Theorem 1].The equivalent problem can be solved with an SDP solver such as SDPT3 or greedily.Source: §2 · p. 36

IV. NUMERICAL EVALUATION

• Phase transitions show poorer recovery with fewer observations and higher rank; NNM-based methods outperform FNM-based methods, with NNM using SDPT3 leading.The survey attributes SDPT3's advantage to convex optimization finding a global optimum, while other methods may converge to local optima.Source: §IV · pp. 37–38, Figure 8 · p. 38
• LMaFit reconstructs a 1000×1000 matrix of rank 5 in about one second, making FNM-based techniques a good choice when exact recovery is unnecessary.Source: §IV · p. 38
• SVT, IRLS-M, ASD, ADMiRA, and LRGeomCG reconstruct 1000×1000 matrices in under a minute, whereas the SDPT3 solver takes more than five minutes.Source: §IV · p. 38, Figure 9 · p. 39
• For impulse-noise images, all LRMC techniques achieve pSNR of at least 52 dB at ρ = 0.3; NNM with SDPT3, SVT, and IRLS-M reach at least 57 dB, with results reported even at ρ = 0.7.Source: §IV · pp. 39–40
• At SNR = 20 dB, TNNR-ADMM performs comparably to NNM-based algorithms, consistent with the noise robustness of its FNM-based cost function.Source: §IV · p. 39, Figure 10 · p. 40
• At SNR = 50 dB, NNM with SDPT3 has the best MSE; at rank(M) = 20, TNNR-ADMM's MSE is around 0.04 versus above 1 for all other algorithms.Source: §IV · p. 39, Figure 11 · p. 40

• When rank is unknown, the survey discusses NNM-based methods such as SDP-based NNM, SVT, and truncated NNM; when rank is known, it covers FNM methods including greedy and alternating-projection algorithms.Source: §V · p. 41
• LRMC design depends on observed-entry sparsity and matrix incoherence, and can exploit PSD, Euclidean-distance, or graph structure.Source: §V · p. 41
• For large-scale matrices, LMaFit and LRGeomCG scale as O(r|Ω|), versus O(n^3) for SDP-based NNM; SDP-based NNM is suggested when recovery accuracy is critical.Source: §V · p. 41
• FNM-based methods such as LMaFit and ADMiRA converge much faster than convex methods, while NNM-based methods are more reliable, making the best trade-off dependent on the setup.Source: §V · p. 41
• Future work should seek recovery-guaranteed algorithms with linear scaling for real-time applications and implementation-friendly algorithms and architectures.Source: §V · p. 42
• Practical matrices may have discrete-valued entries rather than random entries, yet no well-known practical guideline or efficient algorithm addresses this case.Source: §V · p. 42
• CNN-based LRMC uses observed entries as labeled training data to reconstruct a matrix from its graph, but specifying graph-edge criteria can be difficult.Source: §V · p. 42
• Generative adversarial networks consisting of a generator and discriminator are proposed as a useful deep-learning direction for addressing graph-modeling challenges.Source: §V · p. 42

APPENDIX A PROOF OF THE SDP FORM OF NNM

• The SDP proof converts NNM into epigraph form and then transforms its constraints into the standard SDP form.The appendix identifies the resulting concise formulation as the desired NNM result.Source: Appendix A · pp. 43–44
• The nuclear-norm constraint ∥X∥∗ ≤ t is represented using symmetric matrices W1 and W2 [21, Lemma 2].This equivalence is used to reformulate the epigraph problem in SDP form.Source: Appendix A · p. 43
• The observed-entry equality constraint is rewritten as scalar inner-product equalities using the extended sampling operator and standard basis matrices.The appendix then expresses the resulting formulation in the concise form identified as the desired result.Source: Appendix A · pp. 43–44

APPENDIX B PERFORMANCE GUARANTEE OF NNM

• NNM uniquely recovers M if a supported certificate Y = UVT + W exists with W ∈ T⊥ and ∥W∥ < 1, and sampling is injective on T [22, Lemma 3.1].These are the two stated uniqueness conditions for the NNM problem.Source: Appendix B · p. 44
• Establishing the certificate and injectivity conditions depends on the observation model and M’s intrinsic coherence; the theorem considers uniform sampling [22, Theorem 1.3].The appendix defines coherence for M’s column and row spaces and specifies coherence properties for the uniform-sampling guarantee.Source: Appendix B · pp. 44–45
• For r ≤ µ0^-1 n^1/5, m ≥ Cµ0γn^1.2r log n suffices for unique NNM recovery with probability at least 1 − βn^-γ [22, Theorem 1.3].The theorem states this improved sampling bound has the same success probability as its earlier bound.Source: Appendix B · p. 45