Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima

• URL: http://arxiv.org/abs/2505.03717v1
• Date: Tue, 06 May 2025 17:43:35 GMT
• Title: Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima
• Authors: Richard Y. Zhang,
• Abstract summary: We deal with the classical low-rank matrix recovery problem.<n>In this paper we investigate whether benign nonnegativeity continues to hold a common rank when the ground truth is recovered.<n>Surprisingly, however, this property fails to extend to the partially-observed case.
• Score: 10.787390511207683
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical low-rank matrix recovery problem is well-known to exhibit \emph{benign nonconvexity} under the restricted isometry property (RIP): local optimization is guaranteed to converge to the global optimum, where the ground truth is recovered. We investigate whether benign nonconvexity continues to hold when the factor matrices are constrained to be elementwise nonnegative -- a common practical requirement. In the simple setting of a rank-1 nonnegative ground truth, we confirm that benign nonconvexity holds in the fully-observed case with RIP constant $\delta=0$. Surprisingly, however, this property fails to extend to the partially-observed case with any arbitrarily small RIP constant $\delta\to0^{+}$, irrespective of rank overparameterization. This finding exposes a critical theoretical gap: the continuity argument widely used to explain the empirical robustness of low-rank matrix recovery fundamentally breaks down once nonnegative constraints are imposed.

Related papers

• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  In this paper, we aim to investigate the sparse low-rank characteristics rectified on non-negative matrices.<n>We propose a novel regularization term incorporating useful structures in clustering and compression tasks.<n>We derive corresponding closed-form solutions while maintaining the $L$-smooth property always holds for any $Lge 1$.
  arXiv  Detail & Related papers  (2025-03-04T08:20:34Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  Sub-gradient method (SubGM) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• Implicit Regularization in Matrix Sensing via Mirror Descent [29.206451882562867]
  We study discrete-time mirror descent applied to the unregularized empirical risk in matrix sensing. We show that gradient descent with full-rank factorized parametrization is a first-order approximation to mirror descent.
  arXiv  Detail & Related papers  (2021-05-28T13:46:47Z)
• Implicit Regularization in ReLU Networks with the Square Loss [56.70360094597169]
  We show that it is impossible to characterize the implicit regularization with the square loss by any explicit function of the model parameters. Our results suggest that a more general framework may be needed to understand implicit regularization for nonlinear predictors.
  arXiv  Detail & Related papers  (2020-12-09T16:48:03Z)
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number [34.0533596121548]
  Many problems in data science can be treated as estimating a low-rank from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss.
  arXiv  Detail & Related papers  (2020-10-26T06:21:14Z)
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle [23.84884127542249]
  Existing results for low-rank matrix recovery largely behaved on quadratic loss. We show that a critical component in provable low-rank recovery with non-quadratic loss is a regularity projection.
  arXiv  Detail & Related papers  (2020-08-31T17:56:04Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.