PaperlayerView exact revision on arXiv

Source-linked AI summary

Incoherence-Optimal Matrix Completion

Yudong Chen

arXiv:1310.0154v4cs.ITcs.LGstat.ML

TL;DR

The paper asks whether joint incoherence is necessary for exact matrix completion and related low-rank problems. It eliminates the condition for matrix completion using ℓ∞,2-type bounds, while showing it remains necessary for polynomial-time low-rank-plus-sparse decomposition under the Planted Clique assumption.

  • Problem

    Previous exact matrix-completion guarantees require standard and joint incoherence, although joint incoherence is unintuitive, restrictive, and lacks a natural interpretation.

  • Method

    The paper removes joint incoherence from matrix-completion guarantees using new ℓ∞,2-type bounds and analyzes its necessity for matrix decomposition under Planted Clique hardness.

  • Results

    For positive semidefinite matrix recovery, sample complexity improves from O(nr^2 log^2 n) to O(nr log^2 n), while the highest allowable rank improves from Θ(√n/log n) to Θ(n/log^2 n).

  • Takeaways & Limitations

    Joint incoherence is unnecessary for matrix completion but unavoidable for polynomial-time low-rank-plus-sparse decomposition under the Planted Clique assumption.

  • Takeaways & Limitations

    In the semi-supervised clustering application, the analysis assumes diagonal entries Mii = 1 are known and exploits the symmetry Mij = Mji.

Abstract

from arXiv · show

This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank $r$ and the matrix dimension $n$ up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from $O(nr^{2}\log^{2}n)$ to $O(nr\log^{2}n)$, and the highest allowable rank from $Θ(\sqrt{n}/\log n)$ to $Θ(n/\log^{2}n)$. The key step in proof is to obtain new bounds on the $\ell_{\infty,2}$-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-$ω(\sqrt{n})$ positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.

1 Introduction

The paper removes joint incoherence from exact matrix completion, achieving near-optimal incoherence-dependent guarantees and improving recovery bounds for positive semidefinite matrices. It develops ℓ∞,2-based analysis, extends the results to related tasks, and shows that joint incoherence remains computationally necessary for low-rank-plus-sparse decomposition.

  • Motivation: Previous exact-completion guarantees required standard and joint incoherence, although joint incoherence is unintuitive, restrictive, and costly for positive semidefinite matrices.For positive semidefinite matrices, previous bounds required observations proportional to nr2 instead of nr.
  • Main result: With Ω(nr log2 n) uniformly sampled entries, standard-incoherent matrices that are not jointly incoherent can be recovered.The result applies, for example, to a positive semidefinite matrix.
  • Main result: O(nr2 log2 n) to O(nr log2 n) reduces the positive-semidefinite recovery sample complexity, while Θ(√n/ log n) to Θ(n/ log2 n) raises the highest allowable rank.The bounds are order-wise optimal in n, r, and incoherence parameters except for a log n factor.
  • Techniques and extensions: The improvements use new ℓ∞,2 matrix-norm bounds within nuclear norm minimization, and extend to SVD projection, structured completion, and semi-supervised clustering.The ℓ∞,2 norm is the maximum of the row and column norms; the related extensions achieve order-wise improvements over existing results.
  • Matrix decomposition: For low-rank-plus-sparse decomposition, joint incoherence is necessary for polynomial-time algorithms under the Planted Clique computational assumption.The paper relates standard incoherence to statistical aspects and joint incoherence to computational aspects.
  • Related work: The work builds on prior matrix-completion and decomposition studies, whose guarantees required joint incoherence or sample complexity at least quadratic in r.It also organizes extensions and proofs across SVD projection, structured completion, decomposition, and discussion sections.

2 Main Results

The paper removes joint incoherence from matrix completion guarantees, retaining only standard incoherence and achieving near-optimal sample complexity. It also establishes optimality in the incoherence parameter, improves recovery guarantees for positive semidefinite matrices, and extends the analysis to related settings.

  • Problem setup: Matrix completion recovers a low-rank matrix from a subset of independently observed entries, commonly via nuclear norm minimization.The observations follow the Bernoulli model, and the objective seeks a unique optimum equal to the unknown matrix.
  • Prior assumptions: Previous guarantees required standard incoherence and joint incoherence, although joint incoherence is restrictive and unintuitive.Standard incoherence limits concentration of row and column spaces, whereas joint incoherence requires left and right singular vectors to be unaligned.
  • Main theorem: The main theorem eliminates joint incoherence and requires only standard incoherence for exact recovery.The theorem applies to the standard nuclear norm minimization approach and recovers matrices that may be standard-incoherent but not jointly incoherent.
  • Optimality: The theorem is order-wise optimal in µ0 up to a log n factor, matching an information-theoretic lower bound with one additional logarithmic factor.Below p ≳ µ0r log(n)/n, standard-incoherent matrices cannot be uniquely determined even with unlimited computational power.

3 Extensions

The paper extends its incoherence-free matrix-completion analysis to SVD projection, structured matrix completion, and semi-supervised clustering. These extensions improve error or sample-complexity guarantees, especially when side information is available.

  • 3.1 Error Bound for SVD Projection: The ℓ∞,2-norm yields a new SVD-projection error bound that improves on the previous bound when p ≳ log2 n/n and ∥M∥∞,2 is sufficiently small.The norm is the maximum of the row and column norms of M.
  • 3.2 Structured Matrix Completion and Semi-Supervised Clustering: The structured matrix-completion formulation incorporates known subspaces containing the matrix’s column and row spaces.The optimization recovers X∗, after which M = ¯UX∗¯V⊤.
  • 3.2 Structured Matrix Completion and Semi-Supervised Clustering: Theorem 2 requires Θ(r¯r log ¯r log n) observations for constant incoherence parameters, compared with the usual Θ(nr log2 n) when ¯r ≪ n.Setting ¯r = n recovers the standard matrix-completion theorem.
  • 3.2 Structured Matrix Completion and Semi-Supervised Clustering: Theorem 2 removes the superfluous joint-incoherence dependence and replaces the prior max-based scaling with a strictly smaller µ0¯µ0 scaling when µ0 ≠ ¯µ0.This improvement applies even in the ideal comparison setting where µ1 = µ0.
  • 3.2.1 Applications to semi-supervised clustering: In semi-supervised clustering, the result allows nmin = Θ(1) and r = Θ(n) when ¯r = n, versus prior requirements nmin = Ω(√n) and r = O(√n).When nmin = √n, the new result requires √n times fewer observations than the previous bound.

4 Incoherence in Matrix Decomposition: Information and Computational Lower Bounds

For low-rank-plus-sparse matrix decomposition, the paper establishes a contrast with matrix completion: joint incoherence is computationally unavoidable under the Planted Clique assumption. Standard and joint incoherence correspond respectively to information-theoretic and computational limits.

  • Problem and computational assumption: The paper studies recovery of a low-rank matrix and a sparse matrix from their sum, using computational hardness to analyze the role of joint incoherence.The hardness reduction connects decomposition to finding planted cliques of size o(√n).
  • Comparison with matrix completion: The ℓ∞ requirement is natural in matrix decomposition because it is dual to the ℓ1 norm used in the convex formulation.This differs from matrix completion, where the paper says the joint-incoherence ℓ∞ requirement lacks natural motivation.
  • Computational lower bound: Under the Planted Clique assumption, no polynomial-time algorithm can solve the decomposition problem without joint incoherence in the stated regimes.The theorem includes both a rank-one case and a case with µ0 ≥ 2.
  • Computational lower bound: The matrix decomposition problem is intractable in general for positive semidefinite matrices with rank r = ω(√n).In this setting, the cited result uses µ1r = µ0r2 ≥ r2.
  • Information and computational limits: The standard incoherence condition gives an information/statistical limit, whereas joint incoherence gives a computational limit for matrix decomposition.The computational limit applies under the planted-clique assumption, while the information limit applies regardless of computational complexity.

5 Proof of Theorem 1

The proof constructs a dual certificate for nuclear-norm minimization using the Golfing Scheme. Its key innovation is bounding certificate errors with the ℓ∞,2 norm rather than relying only on entrywise ℓ∞ bounds.

  • Proof strategy: The proof’s main innovation is using ℓ∞,2 bounds to establish the dual-certificate condition needed for unique optimality.The paper contrasts this with previous analyses based solely on the ℓ∞ norm.
  • Proof strategy: Convex analysis reduces exact recovery to constructing a dual certificate satisfying several subgradient-type conditions.One condition requires the certificate’s spectral norm to be small.
  • Iterative control: The proof repeatedly applies the norm lemmas across the sampling sets to control the certificate iterates and complete Theorem 1.The argument also invokes standard approximate-isometry and ℓ∞ bounds under the theorem’s sampling conditions.
  • Dual certificate construction: The Golfing Scheme constructs the certificate by partitioning the observed entries into k0 = 20 log n independent sampling sets.The certificate is defined as the final iterate Wk0 and automatically satisfies PΩ(Y) = Y.
  • Norm bounds: A new lemma bounds the spectral norm of (RΩ−I)Z using both ℓ∞,2 and ℓ∞ norms, producing tighter control than prior ℓ∞-only bounds.This bound is applied to the summands arising during certificate construction.

6 Discussion

The discussion attributes the matrix-completion improvements to ℓ∞,2-type bounds, which capture the relative importance of rows and columns. It also contrasts matrix completion with decomposition, where joint incoherence remains computationally unavoidable.

  • Discussion: The paper contrasts the eliminated joint-incoherence requirement in matrix completion with its unavoidable role in polynomial-time matrix decomposition.The decomposition conclusion is based on the computational hardness assumption of the Planted Clique problem.
  • Discussion: The paper’s matrix-completion improvements come from ℓ∞,2-type bounds, which are described as natural for low-rank matrices because they capture row and column importance.The paper leaves broader applicability of these techniques as an open question.

A Proof of Proposition 2

The proof establishes uniqueness of M as the optimum by constructing a nuclear-norm subgradient and showing the objective gap is strictly positive for every other feasible solution.

  • Subgradient argument: A spectral-norm dual certificate G supplies a nuclear-norm subgradient at M for analyzing any feasible X.G satisfies ∥P_T⊥G∥=1 and attains the nuclear-norm dual pairing on P_T⊥(X−M).
  • Subgradient argument: The sampling constraint makes the certificate orthogonal to X−M, yielding ⟨Y, X−M⟩=0.
  • Subgradient argument: Conditions 1 and 2, together with Lemma 5, provide the inequalities needed to lower-bound the objective difference.
  • Strict positivity: The resulting right-hand side is strictly positive whenever X is feasible and X≠M, because otherwise the operator-norm assumption is contradicted.
  • Strict positivity: M is therefore the unique optimum.

B Proofs of Technical Lemmas in Section 5

The technical lemmas control sampling operators using incoherence-based bounds and the matrix Bernstein inequality, followed by high-probability and union-bound arguments.

  • Concentration tools: The technical proofs rely on the matrix Bernstein inequality for independent, bounded, zero-mean random matrices.The theorem is restated with variance and almost-sure norm parameters.
  • Incoherence bounds: Projection-based bounds follow from the definition of P_T and the standard incoherence condition.
  • Sampling estimates: Columns of sampled projection operators are represented using independent random vectors, enabling matrix Bernstein estimates.
  • Sampling estimates: The resulting bounds use the sampling-probability assumption and incoherence condition, then extend across indices through union bounds.

C Proof of Corollary 1

The corollary proof first controls the observed row and column degrees, then uses singular-value perturbation bounds to derive the stated conclusion.

  • Degree control: 2pn bounds the observed-entry degrees of the rows and columns of P_ΩM with high probability.Standard Bernstein concentration and a union bound provide this degree control.
  • Singular-value control: Weyl’s inequality bounds the singular values indexed from r+1 through n using the singular values of M and the sampled approximation.
  • Singular-value control: The rank bound on M−T_r(M̃_Ω), together with the preceding estimates, completes the corollary.

D Proof of Theorem 2

Theorem 2 is proved by adapting the earlier dual-certificate argument to redefined tangent-space projections and a golfing-scheme certificate, ultimately establishing unique optimality.

  • Projection framework: The proof redefines the two projections and follows the structure of the proof of Theorem 1.
  • Projection framework: The projections P_T and P_T⊥ decompose matrices relative to the original and enlarged singular-vector spaces.Their sum recovers the projection onto the enlarged row and column spaces.
  • Optimality conditions: Proposition 3 characterizes unique optimality through a subgradient condition involving the candidate solution X*=Ū^⊤M V̄.
  • Optimality conditions: The proof bounds the tangent and orthogonal components of a feasible perturbation using the sampling operator and the proposition’s conditions.
  • Dual certificate: A golfing-scheme construction produces Y with the required sampling support, while Lemmas 7–9 establish the needed high-probability bounds.
  • Dual certificate: The incoherence conditions complete Condition 2(b), and X* is consequently the unique optimal solution.

D.1 Proof of Lemma 6

The lemma is proved by representing sampling deviations with independent random operators or variables, then applying Bernstein inequalities and union bounds under a lower bound on p.

  • Operator-norm bounds: Matrix Bernstein bounds the operator deviations after expressing sampling terms through independent zero-mean self-adjoint operators.The proof invokes the matrix Bernstein inequality after defining sampling operators and establishing variance bounds.
  • Operator-norm bounds: The argument controls projection-related quantities using the assumed relations among incoherence parameters and the sampling probability p.The proof explicitly uses µ0r ≤ ¯µ0¯r and assumes p ≥ c0.
  • Columnwise bounds: Columnwise deviations are handled by treating independent vectors as n × 1 matrices and applying matrix Bernstein, followed by a union bound over all column indices.The lemma obtains analogous bounds for the relevant column quantities with sufficiently large c0.
  • Entrywise bounds: Entrywise deviations are written as sums of independent zero-mean variables, bounded with Bernstein’s inequality, and extended to all entries by a union bound.The resulting entrywise bound is stated to hold with high probability when c0 is sufficiently large.

E.1 Part 1 of the theorem

The theorem’s first part reduces planted clique to matrix decomposition through subsampling and then constructs indistinguishable low-rank instances to bound the information available from observations.

  • Planted-clique reduction: The planted clique instance is encoded as a rank-one matrix L* plus a sparse residual, with L* satisfying both standard and joint incoherence conditions.The construction starts from the graph adjacency matrix and subtracts the clique matrix before subsampling.
  • Planted-clique reduction: A polynomial-time matrix-decomposition algorithm recovering L* would recover planted cliques of size n_min ≤ n, contradicting the stated planted-clique assumption.The reduction uses subsampling and transfers the recovery guarantee to planted-clique detection.
  • Information-theoretic bound: The information-theoretic construction uses M = n/2 candidate matrices obtained by swapping one row and column of a block-diagonal rank-r matrix.Each candidate preserves rank r and satisfies the standard incoherence condition with parameter µ0.
  • Information-theoretic bound: The sparse component is generated conditionally on each candidate, with Bernoulli-supported values differing inside and outside the support of L*.The observation matrix is A = L* + S*; the residual uses τ = 1/3 on supported entries and outside-support entries.
  • Information-theoretic bound: The mutual-information calculation bounds I(L*; A) by K + 1, after which Fano’s inequality lower-bounds the error of any measurable estimator.The KL-divergence calculation uses log x ≤ x−1 before applying Fano’s inequality.
Loading 1310.0154v4…