Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion

We consider robust low rank matrix estimation when random noise is heavy-tailed and output is contaminated by adversarial noise. Under the clear conditions, we firstly attain a fast convergence rate for low rank matrix estimation including compressed sensing and matrix completion with convex estimators.

• Publication year

  2020

• Venue

  arXiv.org

• Publication date

  2020-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2010.13018
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Robust linear regression: optimal rates in polynomial time

  2020cited by this paper
• A Robust Univariate Mean Estimator is All You Need

  2020cited by this paper
• All-in-one robust estimator of the Gaussian mean

  2020cited by this paper
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion

  2020influential reference
• High-Dimensional Probability: An Introduction with Applications in Data Science

  2020cited by this paper
• A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

  2019cited by this paper
• Robust multivariate mean estimation: The optimality of trimmed mean

  2019cited by this paper
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

  2019cited by this paper
• Faster Algorithms for High-Dimensional Robust Covariance Estimation

  2019cited by this paper
• Robust sub-Gaussian estimation of a mean vector in nearly linear time

  2019cited by this paper
• Sub‐Weibull distributions: Generalizing sub‐Gaussian and sub‐Exponential properties to heavier tailed distributions

  2019cited by this paper
• Fast Mean Estimation with Sub-Gaussian Rates

  2019cited by this paper
• Outlier-robust estimation of a sparse linear model using 𝓁1-penalized Huber's M-estimator

  2019influential reference
• Robust inference via multiplier bootstrap

  2019influential reference
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

  2019cited by this paper
• ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels

  2019cited by this paper
• Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering

  2019cited by this paper
• Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence

  2018cited by this paper
• Robust estimation via robust gradient estimation

  2018cited by this paper
• High Dimensional Robust Sparse Regression

  2018influential reference
• Efficient Algorithms and Lower Bounds for Robust Linear Regression

  2018cited by this paper
• Robust moment estimation and improved clustering via sum of squares

  2018cited by this paper
• Mean estimation with sub-Gaussian rates in polynomial time

  2018cited by this paper
• High-Dimensional Robust Mean Estimation in Nearly-Linear Time

  2018cited by this paper
• Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression

  2018cited by this paper
• High-Dimensional Probability

  2018cited by this paper
• Sub-Gaussian estimators of the mean of a random vector

  2017cited by this paper
• Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions

  2017influential reference
• Adaptive Huber Regression

  2017cited by this paper
• Computationally Efficient Robust Sparse Estimation in High Dimensions

  2017cited by this paper
• Robust regression via mutivariate regression depth

  2017cited by this paper
• Being Robust (in High Dimensions) Can Be Practical

  2017cited by this paper
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

  2017cited by this paper
• Agnostic Estimation of Mean and Covariance

  2016cited by this paper
• A SHRINKAGE PRINCIPLE FOR HEAVY-TAILED DATA: HIGH-DIMENSIONAL ROBUST LOW-RANK MATRIX RECOVERY.

  2016influential reference
• Adaptive confidence sets for matrix completion

  2016cited by this paper
• Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries

  2016cited by this paper
• Regularization and the small-ball method I: sparse recovery

  2016cited by this paper
• Learning from untrusted data

  2016cited by this paper
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cited by this paper
• Robust low-rank matrix estimation

  2016cited by this paper
• Nearly Optimal Robust Matrix Completion

  2016cited by this paper
• Slope meets Lasso: Improved oracle bounds and optimality

  2016influential reference
• SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax

  2015cited by this paper
• Statistical consistency and asymptotic normality for high-dimensional robust M-estimators

  2015cited by this paper
• Sub-Gaussian mean estimators

  2015cited by this paper
• Robust reduced-rank regression

  2015influential reference
• I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.

  2015influential reference
• Robust covariance and scatter matrix estimation under Huber’s contamination model

  2015cited by this paper
• Matrix completion by singular value thresholding: sharp bounds

  2015cited by this paper
• Robust matrix completion

  2014cited by this paper
• Fast Exact Matrix Completion with Finite Samples

  2014cited by this paper
• Concentration inequalities and moment bounds for sample covariance operators

  2014cited by this paper
• Upper bounds on product and multiplier empirical processes

  2014cited by this paper
• SLOPE-ADAPTIVE VARIABLE SELECTION VIA CONVEX OPTIMIZATION.

  2014influential reference
• Robust Sparse Regression under Adversarial Corruption

  2013influential reference
• Matrix completion via max-norm constrained optimization

  2013cited by this paper
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

  2013cited by this paper
• Concentration Inequalities: A Nonasymptotic Theory of Independence

  2013influential reference
• Matrix estimation by Universal Singular Value Thresholding

  2012cited by this paper
• Subgaussian random variables : An expository note

  2012cited by this paper
• Noisy low-rank matrix completion with general sampling distribution

  2012cited by this paper
• Matrix Completion With Column Manipulation: Near-Optimal Sample-Robustness-Rank Tradeoffs

  2011cited by this paper
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements

  2011cited by this paper
• Robust Lasso With Missing and Grossly Corrupted Observations

  2011cited by this paper
• Restricted Eigenvalue Properties for Correlated Gaussian Designs

  2010influential reference
• Nuclear norm penalization and optimal rates for noisy low rank matrix completion

  2010cited by this paper
• Nearly unbiased variable selection under minimax concave penalty

  2010cited by this paper
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

  2010cited by this paper
• Outlier Detection Using Nonconvex Penalized Regression

  2010cited by this paper
• Matrix Completion With Noise

  2009cited by this paper
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• Estimation of high-dimensional low-rank matrices

  2009cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Compressed sensing

  2006cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Addendum: Regularization and variable selection via the elastic net

  2005cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties

  2001cited by this paper
• About the constants in Talagrand's concentration inequalities for empirical processes

  2000influential reference
• Multivariate Reduced-Rank Regression: Theory and Applications

  1998cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper

• No citing papers are available for this paper.