Robust Matrix Sensing in the Semi-Random Model
Authors: Xing Gao, Yu Cheng
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we relax the assumptions and study new approaches for matrix sensing in a semi-random model where an adversary can add any number of arbitrary sensing matrices. More precisely, the problem is to recover a low-rank matrix X from linear measurements bi = Ai, X , where an unknown subset of the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the Ai s are chosen adversarially. It is known that in the semi-random model, existing non-convex objectives can have bad local optima. To fix this, we present a descent-style algorithm that provably recovers the ground-truth matrix X . For the closely-related problem of semirandom matrix completion, prior work [CG18] showed that all bad local optima can be eliminated by reweighting the input data. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which is a condition that is NP-hard to check. Instead, we build on the framework proposed in [KLL+23] for semi-random sparse linear regression, where the algorithm in each iteration reweights the input based on the current solution, and then takes a weighted gradient step that is guaranteed to work well locally. Our analysis crucially exploits the connection between sparsity in vector problems and lowrankness in matrix problems, which may have other applications in obtaining robust algorithms for sparse and low-rank problems. |
| Researcher Affiliation | Academia | Xing Gao University of Illinois at Chicago xgao53@uic.edu Yu Cheng Brown University yu_cheng@brown.edu |
| Pseudocode | Yes | Algorithm 1: Semi Random Matrix Sensing(R0, ϵ, δ, A, b), Algorithm 2: Halve Error(Xin, R, O, δ, A, b), Algorithm 3: O(A, u, δ) |
| Open Source Code | No | The paper does not contain any statements about making source code publicly available or links to code repositories. |
| Open Datasets | No | The paper is theoretical and does not mention using any specific datasets for training or evaluation. Theorem 1.1 mentions "Gaussian design" but this is a theoretical assumption for the sensing matrices, not a dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation on specific datasets with train/validation/test splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers required for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and does not include details on an experimental setup, such as hyperparameters or system-level training settings. |