Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, nonsmooth penalty formulations do not suffer from the same type of ill-conditioning. Consequently, standard algorithms for nonsmooth optimization, such as subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. Moreover, nonsmooth formulations are naturally robust against outliers. Our framework subsumes such important computational tasks as phase retrieval, blind deconvolution, quadratic sensing, matrix completion, and robust PCA. Numerical experiments on these problems illustrate the benefits of the proposed approach.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionRetrievalMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast Composite Optimization and Statistical Recovery in Federated Learning
As a prevalent distributed learning paradigm, Federated Learning (FL) trains a global model on a massive amount of devices with infrequent communication. This paper investigates a class of composite optimization and stat…
Federated LearningAn inexact LPA for DC composite optimization and application to matrix completions with outliers
This paper concerns a class of DC composite optimization problems which, as an extension of convex composite optimization problems and DC programs with nonsmooth components, often arises in robust factorization models of…
A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion
Matrix learning is at the core of many machine learning problems. A number of real-world applications such as collaborative filtering and text mining can be formulated as a low-rank matrix completion problem, which recov…
Collaborative FilteringLow-Rank Matrix CompletionMatrix CompletionFast Algorithm for Low-rank matrix recovery in Poisson noise
This paper describes a fast algorithm for recovering low-rank matrices from their linear measurements contaminated with Poisson noise: the Poisson noise Maximum Likelihood Singular Value thresholding (PMLSV) algorithm. W…
Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
Many problems in statistics and machine learning require the reconstruction of a rank-one signal matrix from noisy data. Enforcing additional prior information on the rank-one component is often key to guaranteeing good …
global-optimization