Unified approach for robust low rank matrix estimation with adversaries.
problem Robust low rank matrix estimation in the presence of adversaries.
method Unified approach combining Huber loss and nuclear norm penalization.
result Sharp estimation error bounds for matrix compressed sensing and completion.
New method for robust matrix completion with mixed data types.
problem Recovering a structured low rank matrix with mixed data types.
method Proposes a computationally feasible statistical approach with strong recovery guarantees for mixed data types.
result Strong recovery guarantees for low rank matrix completion with mixed data types.
Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.
problem Robust low-rank matrix recovery in the presence of corrupted measurements.
method Proposed Sign-RIP, a robust restricted isometry property.
result Sign-RIP guarantees uniform convergence of subdifferentials in robust low-rank matrix recovery.
Paper proposes fast, robust methods for low-rank matrix recovery.
problem Estimating low-rank matrices from incomplete or corrupted data.
method Scaled subgradient methods for nonsmooth, nonconvex formulations.
result Methods converge almost dimension-free and condition-number independent.
Due to the insufficient measurements in the distribution system state estimation (DSSE), full observability and redundant measurements are difficult to achieve without using the pseudo measurements. The matrix completion state estimation (MCSE) combines the matrix completion and power system model to estimate voltage b…
We solve robust regression and matrix completion problems with sparse and low-rank models.
problem Adversarial contamination and noisy matrix completion in high-dimensional settings.
method Subgaussian statistical learning framework, trace-regression with matrix decomposition, novel Huber-type loss.
result Near-optimal estimation rates for robust regression and matrix completion.
ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.
problem Efficiently solving ill-conditioned low-rank matrix estimation problems.
method Scaled Gradient Descent (ScaledGD) with adaptive pre-conditioners.
result Linear convergence rate independent of condition number, low per-iteration cost.
New algorithms improve RPCA for large matrices with upper rank bounds.
problem Efficiently decompose large matrices into low-rank and sparse parts.
method Combine regularization and matrix multiplication approaches with upper rank bounds.
result Proposed algorithms are faster and more robust than existing methods.
New method improves robust low-rank matrix completion for computer vision.
problem Robust low-rank matrix completion for partially observed data.
method Formulated as a nonsmooth Riemannian optimization problem over Grassmann manifold, solved with an alternating manifold proximal gradient continuation method.
result Demonstrated advantages over existing approaches in background extraction from surveillance videos.
Framework for robust matrix estimation with side information.
problem High-dimensional matrix estimation with restrictive structure.
method Flexible framework decomposing matrix into four components: interaction, row, column, and residual.
result Improved imputation accuracy and treatment-effect estimation with side information.
Paper proposes a new method to separate low rank and sparse matrices without bias.
problem Recovering low rank and sparse matrices from measurements.
method Uses nonconvex regularizers and alternating proximal gradient descent.
result Error bounds for the algorithm applied to sparse optimization, matrix completion, and robust PCA.
Develops PRPCA for smooth image recovery combining low-rank and smoothness.
problem Image matrix recovery under low-rank and smoothness assumptions.
method Projected Robust PCA (PRPCA) framework combining low-rank and smoothness.
result Explicit statistical guarantees for PRPCA, reducing matrix dimensionality.
Recovery of low-rank matrices has recently seen significant activity in many areas of science and engineering, motivated by recent theoretical results for exact reconstruction guarantees and interesting practical applications. A number of methods have been developed for this recovery problem. However, a principled meth…
A new algorithm improves both computational efficiency and statistical optimality for robust low-rank matrix and tensor estimation.
problem Challenges in low-rank matrix estimation under heavy-tailed noise, both computationally and statistically.
method Riemannian sub-gradient (RsGrad) algorithm, which is computationally efficient and statistically optimal.
result RsGrad achieves linear convergence and statistical optimality for robust loss functions under Gaussian and heavy-tailed noise.
Estimation of low-rank matrices is of significant interest in a range of contemporary applications. In this paper, we introduce a rank-one projection model for low-rank matrix recovery and propose a constrained nuclear norm minimization method for stable recovery of low-rank matrices in the noisy case. The procedure is…
Paper tackles robust matrix completion with heavy-tailed noise.
problem Estimating a low-rank matrix from noisy incomplete data.
method Adaptive Huber loss for robustness, nonconvex algorithm with spectral initialization.
result Achieves minimax-optimal statistical estimation error under bounded second moment condition.
Robust low-rank matrix estimation is a topic of increasing interest, with promising applications in a variety of fields, from computer vision to data mining and recommender systems. Recent theoretical results establish the ability of such data models to recover the true underlying low-rank matrix when a large portion o…
Study robust recovery of low-rank matrices from corrupted measurements without rank prior.
problem Robust recovery of low-rank matrices from corrupted Gaussian measurements with unknown rank.
method Subgradient method with diminishing stepsizes for nonconvex nonsmooth problem.
result Subgradient method converges to exact low-rank solution at sublinear rate under RDPP condition.
Robust PCA is a widely used statistical procedure to recover a underlying low-rank matrix with grossly corrupted observations. This work considers the problem of robust PCA as a nonconvex optimization problem on the manifold of low-rank matrices, and proposes two algorithms (for two versions of retractions) based on ma…
New spectral methods improve matrix estimation in RL with low-rank structure.
problem Estimating matrices with low-rank structure in reinforcement learning.
method Spectral-based matrix estimation approaches.
result Spectral methods efficiently recover singular subspaces and minimize entry-wise error.
Sub-gradient method recovers low-rank matrices robustly from noisy measurements.
problem Recovering low-rank matrices from noisy measurements with unknown rank.
method Sub-gradient method with small initialization, robust to over-parameterization and noise.
result Sub-gradient method converges exponentially fast to the true solution under noisy and over-parameterized conditions.
Novel method for efficient low-rank matrix estimation and bandit algorithms.
problem Low-rank matrix estimation and bandit problems.
method LowPopArt method for low-rank matrix estimation and novel experimental design criterion.
result Improved recovery guarantees and regret bounds for low-rank bandit algorithms.
IRCUR accelerates RPCA by using CUR decomposition for efficient low rank estimation.
problem Dimension reduction in robust principal component analysis.
method IRCUR employs CUR decomposition to update the low rank component efficiently.
result IRCUR achieves significant computational efficiency compared to existing algorithms.
New algorithm improves deep learning models' robustness without sacrificing accuracy.
problem Low-rank methods compromise model robustness against adversarial perturbations.
method Robust low-rank training via approximate orthonormal constraints.
result Ensures well-conditioning and better adversarial robustness without sacrificing model accuracy.
Gradient descent recovers low-rank matrices from corrupted measurements with double over-parameterization.
problem Robust recovery of low-rank matrices from grossly corrupted measurements.
method Gradient descent with discrepant learning rates for double over-parameterized models.
result Gradient descent with discrepant learning rates provably recovers the underlying matrix without prior knowledge on rank or sparsity.
Flat minima lead to better generalization in low-rank matrix recovery models.
problem Understanding why flat minima generalize well in overparameterized models.
method Analysis of overparameterized matrix and bilinear sensing, robust PCA, covariance matrix estimation, and neural networks with quadratic activation functions.
result Flat minima, measured by the trace of the Hessian, exactly recover the ground truth in low-rank matrix recovery models under standard statistical assumptions.
Low-rank matrix approximations are often used to help scale standard machine learning algorithms to large-scale problems. Recently, matrix coherence has been used to characterize the ability to extract global information from a subset of matrix entries in the context of these low-rank approximations and other sampling-…
We present a unified framework for low-rank matrix estimation with nonconvex penalties. We first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuclear norm penalty. Moreover, we rigorously show that under a certain condition on the magnitude of t…
This work improves robustness guarantees for neural networks using low rank representations.
problem Certified robustness to adversarial perturbations in neural networks.
method Low rank representations to provide improved robustness guarantees.
result Improved robustness guarantees for ℓ∞ perturbations using natural low rank representations. Paper analyzes robust matrix completion with efficient nonconvex method and leave-one-out analysis.
problem Robust matrix completion with sparse noise.
method Alternates between projected gradient step for low-rank and thresholding step for sparse noise.
result Achieves linear convergence for general thresholding functions.
New framework explains why nonconvex methods work well in low-rank matrix estimation.
problem Nonconvex low-rank matrix estimation problems in machine learning.
method Developed a theoretical framework revealing a benign regularizer.
result Nonconvex procedures can behave well due to a disguised convexity.
New method solves robust matrix completion using nonlinear equations.
problem Recover low rank and sparse matrices from incomplete observations.
method Transforms problem into solving a system of nonlinear equations, then uses the alternative direction method.
result Algorithm converges linearly to the true solution under proper assumptions.
We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation X of the sum of an approximately) low rank matrix Θ⋆ with a second matrix Γ⋆ endowed with a complementary …
Most recent results in matrix completion assume that the matrix under consideration is low-rank or that the columns are in a union of low-rank subspaces. In real-world settings, however, the linear structure underlying these models is distorted by a (typically unknown) nonlinear transformation. This paper addresses the…
We propose a unified framework to solve general low-rank plus sparse matrix recovery problems based on matrix factorization, which covers a broad family of objective functions satisfying the restricted strong convexity and smoothness conditions. Based on projected gradient descent and the double thresholding operator, …
We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearl…
This paper proposes robust matrix variate regression models with rank constraints and vector regularization.
problem High dimensional and noisy matrix-valued predictors in regression models.
method Rank constraint, vector regularization, alternating projected gradient descent algorithm.
result The proposed method achieves the minimax rate of estimation errors.
This paper develops a new class of nonconvex regularizers for low-rank matrix recovery. Many regularizers are motivated as convex relaxations of the matrix rank function. Our new factor group-sparse regularizers are motivated as a relaxation of the number of nonzero columns in a factorization of the matrix. These nonco…
In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios th…
In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios th…
UA-LQE improves value function learning by selectively erasing uncertain entries in Q-matrix.
problem Improving value function learning in complex reinforcement learning tasks.
method Uncertainty-aware low-rank Q-matrix estimation (UA-LQE) algorithm.
result UA-LQE selectively erases uncertain entries in Q-matrix to improve value function approximation.
New method normalizes matrix features for robust low-rank approximation.
problem Robust feature normalization for low-rank matrix approximation.
method Learn quantile normalization operators jointly with matrix factorization.
result Improves quality of low-rank representation of data.
SGD with mini-batches can solve convex low-rank matrix problems efficiently.
problem Solving large-scale convex low-rank matrix problems efficiently.
method Stochastic Gradient Descent with mini-batches and low-rank projections.
result SGD with mini-batches produces low-rank iterates with high probability.
Novel LRMC tackles missing data and outliers in large-scale low-rank data recovery.
problem Missing data and extreme outliers in low-rank data analysis.
method Learned Robust Matrix Completion (LRMC) using deep unfolding and flexible neural network framework.
result LRMC achieves optimum performance with low computational complexity and linear convergence.
This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-unif…
New guarantees for recovering matrices as low-rank plus sparse from fewer measurements.
problem Recovering matrices as the sum of a low-rank and sparse matrix from a limited number of measurements.
method Developed guarantees for recovery of low-rank plus sparse matrices from O(r(m+n−r)+s)log(mn/s) measurements, using semidefinite programming and gradient descent algorithms. result Guarantees for recovery of low-rank plus sparse matrices from fewer measurements than previously possible.
Paper relaxes factor analysis for noisy data, improving robustness.
problem Challenges in finding robust low dimensional approximations for data with heteroskedastic noise.
method Introduces a relaxed version of Minimum Trace Factor Analysis (MTFA) as a convex optimization method.
result Effective at not overfitting to heteroskedastic perturbations and addressing common issues in factor analysis.
This paper considers the problem of estimating a low-rank matrix from the observation of all or a subset of its entries in the presence of Poisson noise. When we observe all entries, this is a problem of matrix denoising; when we observe only a subset of the entries, this is a problem of matrix completion. In both case…