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

Abstract

We consider robust low rank matrix estimation as a trace regression when outputs are contaminated by adversaries. The adversaries are allowed to add arbitrary values to arbitrary outputs. Such values can depend on any samples. We deal with matrix compressed sensing, including lasso as a partial problem, and matrix completion, and then we obtain sharp estimation error bounds. To obtain the error bounds for different models such as matrix compressed sensing and matrix completion, we propose a simple unified approach based on a combination of the Huber loss function and the nuclear norm penalization, which is a different approach from the conventional ones. Some error bounds obtained in the present paper are sharper than the past ones.

The lasso part of this manuscript with contaminated input as well as output is investigated in arXiv:2208.11592. This manuscript will not be submitted for publications

References in corpus (11)

• Nearly unbiased variable selection under minimax concave penalty
• Matrix estimation by Universal Singular Value Thresholding
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Being Robust (in High Dimensions) Can Be Practical
• High Dimensional Robust Sparse Regression
• Robust regression with covariate filtering: Heavy tails and adversarial contamination
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Optimal Robust Linear Regression in Nearly Linear Time
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability