Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number

• URL: http://arxiv.org/abs/2010.13364v2
• Date: Thu, 22 Apr 2021 15:09:42 GMT
• Title: Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Authors: Tian Tong, Cong Ma, Yuejie Chi
• Abstract summary: 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.
• Score: 34.0533596121548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many problems in data science can be treated as estimating a low-rank matrix 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 function, such as the residual sum of squares. While tremendous progresses have been made in recent years, the natural smooth formulation suffers from two sources of ill-conditioning, where the iteration complexity of gradient descent scales poorly both with the dimension as well as the condition number of the low-rank matrix. Moreover, the smooth formulation is not robust to corruptions. In this paper, we propose scaled subgradient methods to minimize a family of nonsmooth and nonconvex formulations -- in particular, the residual sum of absolute errors -- which is guaranteed to converge at a fast rate that is almost dimension-free and independent of the condition number, even in the presence of corruptions. We illustrate the effectiveness of our approach when the observation operator satisfies certain mixed-norm restricted isometry properties, and derive state-of-the-art performance guarantees for a variety of problems such as robust low-rank matrix sensing and quadratic sampling.

Related papers

• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• A Novel Maximum-Entropy-Driven Technique for Low-Rank Orthogonal Nonnegative Matrix Factorization with $\ell_0$-Norm sparsity Constraint [0.0]
  In data-driven control and machine learning, a common requirement involves breaking down large matrices into smaller, low-rank factors. This paper introduces an innovative solution to the orthogonal nonnegative matrix factorization (ONMF) problem. The proposed method achieves comparable or improved reconstruction errors in line with the literature.
  arXiv  Detail & Related papers  (2022-10-06T04:30:59Z)
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery [37.05862765171643]
  We consider a robust factorization of a low-rank matrix with no prior knowledge on the rank. We show that our particular design of diminishing the size of the matrix effectively prevents overfitting under overized models.
  arXiv  Detail & Related papers  (2021-09-23T05:54:46Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers [6.320141734801679]
  We show that a simple sub-gradient method converges to the true low-rank solution efficiently. We also build upon a new notion of restricted isometry property, called sign-RIP, to prove the robustness of the method.
  arXiv  Detail & Related papers  (2021-02-05T02:52:00Z)
• 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)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  Low-rank matrix estimation converges convex problem that finds numerous applications in signal processing, machine learning and imaging science. We show that ScaledGD achieves the best of the best in terms of the number of the low-rank matrix. Our analysis is also applicable to general loss that are similar to low-rank gradient descent.
  arXiv  Detail & Related papers  (2020-05-18T17:17: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.