Source-linked AI summary
Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
Nicolas Gillis, François Glineur
TL;DR
The paper studies the computational complexity of weighted low-rank approximation, motivated by applications involving weighted or missing matrix entries. Using reductions from the maximum-edge biclique problem, it proves NP-hardness even for rank-one approximation with positive or binary weights.
Problem
The paper asks whether rank-one low-rank approximation remains computationally tractable when matrix entries have weights or are missing.
Method
The proofs reduce the maximum-edge biclique problem to weighted low-rank approximation with positive weights and to the missing-data setting with binary weights.
Results
Rank-one WLRA is NP-hard to approximate for strictly positive weights and binary weights, with objective accuracies below 2^-11(mn)^-6 and 2^-12(mn)^-7, respectively.
Takeaways & Limitations
The result extends NP-hardness to rank-one weighted NMF and rank-one NMF with missing data, unlike unweighted rank-one NMF, which is polynomially solvable.
Takeaways & Limitations
The approximation-accuracy bounds decrease with matrix dimensions, and strengthening these bounds remains open.
Abstract
from arXiv · showhide
Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we study the computational complexity of WLRA and prove that it is NP-hard to find an approximate solution, even when a rank-one approximation is sought. Our proofs are based on a reduction from the maximum-edge biclique problem, and apply to strictly positive weights as well as binary weights (the latter corresponding to low-rank matrix approximation with missing data).
1 Introduction
Weighted low-rank approximation extends low-rank dimensionality reduction by assigning differing importance to matrix entries, including zero weights for missing data. The paper formalizes its rank-one computational complexity and proves strong NP-hardness results for positive and binary weights.
- Low-rank matrix approximation is widely used for linear dimensionality reduction and appears in variants such as PCA and nonnegative matrix factorization.
- Weights can reflect unequal sampling or variance, account for missing entries through zero weights, or emphasize localized regions of the data.The paper gives examples from digital filter design, microarray analysis, collaborative filtering, computer vision, and image processing.
- Weighted low-rank approximation (WLRA) seeks a rank-at-most-r matrix that minimizes weighted Frobenius error relative to an input matrix.The formulation uses a nonnegative m-by-n weight matrix and can represent the approximation as UV^T.
- The paper analyzes rank-one WLRA because its computational complexity had not previously been studied formally despite suspected NP-hardness.The results also generalize to any fixed rank r.
- Rank-one WLRA is NP-hard to approximate with accuracy less than 2^-11(mn)^-6 for binary input matrices and strictly positive weights.A separate theorem establishes the analogous result with accuracy less than 2^-12(mn)^-7 for entries in [0,1] and binary weights.
- The proofs reduce the maximum-edge biclique problem to the two rank-one approximation problems and conclude with open questions about weight-ratio thresholds and higher-rank weight matrices.
2 Previous Results
Prior work established that weighted low-rank approximation can differ sharply from unweighted approximation, especially with missing data, but did not formally settle fixed-rank complexity. The paper reviews these distinctions and motivating examples before isolating rank-one WLRA as the unresolved case.
- Weighted versus unweighted approximation: Unweighted low-rank approximation is efficiently solved by SVD, whereas weighted WLRA may have nonglobal local minima.The weighted objective can therefore have optimization behavior absent from the all-ones weight case.
- Rank-one structure: For nonnegative matrices, rank-one WLRA solutions may be taken nonnegative and normalized so that only two degrees of freedom remain.Taking component-wise absolute values cannot worsen the approximation, and scaling permits ||u||2 = 1.
- Missing-data formulation: Binary weights make WLRA equivalent to approximating a matrix with missing entries, connecting it to low-rank matrix completion.Known entries correspond to nonzero weights, while zero weights represent missing values.
- Fixed-rank complexity: NP-hardness of matrix completion does not establish NP-hardness for fixed-rank WLRA, particularly when the target rank is one.The rank-one matrix-completion feasibility question can be checked easily, so a separate complexity argument is required.
- Related applications: A structure-from-motion formulation is a rank-four WLRA problem with binary weights, but its hardness likewise says nothing about rank-one WLRA.The rank mismatch prevents directly transferring that result to the rank-one case.
- Weight assumptions: With zero weights, WLRA's bounded infimum may be unattained, unlike the strictly positive-weight case where the weighted norm ensures attainment.This motivates analyzing positive and binary weight matrices separately.
3 Complexity of rank-one (WLRA)
The paper reduces the maximum-edge biclique problem to rank-one weighted low-rank approximation, establishing NP-hardness for both positive weights and missing-data formulations. The construction uses large penalties on zero entries and extends to every fixed rank.
- Reduction framework: Polynomial-time reductions from the maximum-edge biclique problem underpin the NP-hardness proofs for rank-one WLRA.MBP asks for a complete bipartite subgraph with the maximum number of edges.
- Reduction framework: The biclique formulation encodes graph nonedges by forbidding selected vertices from appearing together, while minimizing edges outside the biclique.Its optimum is |E| − |E*|, where |E*| is the size of an optimal biclique.
- Positive weights: Large penalties on zero entries make the weighted rank-one objective approach the biclique objective as the penalty parameter d increases.This connects the weighted approximation problem to a quadratic penalty formulation of MBP.
- Positive weights: The reduction proves approximate rank-one WLRA is NP-hard for positive weights, including the stated inverse-polynomial accuracy bounds.The result applies to binary matrices M with strictly positive weights W.
- Missing data and higher rank: The missing-data construction yields the corresponding NP-hardness result with binary weights and bounded matrix entries, and the rank-one result generalizes to any fixed rank.The reductions remain polynomial because the constructed matrix dimensions and weight descriptions grow polynomially.
4 Concluding Remarks
The paper establishes NP-hardness for approximate WLRA and related weighted factorization problems, then identifies boundary cases and unresolved gaps in approximation strength and weight-matrix structure.
- Conclusions: Approximate WLRA is NP-hard already at rank one for both positive and binary weights, with binary weights modeling missing data.The result also corresponds to low-rank matrix completion with noise and PCA with missing data.
- Conclusions: The hardness results extend to a broader quadratic formulation and to weighted nonnegative matrix factorization.The WLRA objective is a special case with diagonal nonnegative quadratic weights, and rank-one solutions for nonnegative data can be assumed nonnegative.
- Conclusions: Rank-one weighted NMF remains NP-hard with positive or missing-data weights, unlike unweighted rank-one NMF, which is polynomially solvable.The contrast concerns fixed rank one; unweighted NMF is separately known to be NP-hard when rank is part of the input.
- Limitations: The approximation guarantee is weak: required objective accuracy decreases with matrix dimensions in proportion to (mn)^−6.The dependence arises from the reduction parameter d and the rounding requirement used to recover the optimal biclique size.
- Open questions: The results do not establish hardness within a constant multiplicative factor, leaving stronger inapproximability reductions as an open direction.The paper suggests combining its reductions with biclique inapproximability results or reducing from other problems.
- Open questions: When all weights are one or the weight matrix has rank one, WLRA is polynomially solvable, whereas general weight matrices yield NP-hardness.The complexity threshold for fixed weight-matrix rank greater than one remains open.