Search for: All records

We study low-rank matrix completion in the semi-random model, where each entry (i, j) is observed independently with an unknown probability p_{i,j} >= p, in contrast to the standard model with a uniform probability p. While prior work has shown that nonconvex approach succeeds in the semi-random model for exact observations (Cheng and Ge, 2018), it remains unclear whether similar guarantees extend to more general observation model, such as noisy or one-bit measurements. In this paper, we give a unified framework for semi-random matrix recovery applicable to a broad family of observation models. Our approach builds on the preprocessing step of Cheng and Ge (2018) to restore regularity conditions that are violated under adversarial sampling, and leverages the primal-dual framework of Zhang et al. (2018b) to obtain near-optimal recovery guarantees. As concrete corollaries, we show that for both noisy and one-bit matrix completion in the semi-random model, after the preprocessing step, every local minimum of the non-convex objective yields an approximate recovery of the ground-truth matrix. 

Low-rank matrix recovery is a fundamental problem in machine learning with numerous applications. In practice, the problem can be solved by convex optimization namely nuclear norm minimization, or by non-convex optimization as it is well-known that for low-rank matrix problems like matrix sensing and matrix completion, all local optima of the natural non-convex objectives are also globally optimal under certain ideal assumptions. In this paper, we 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^\star$$ from linear measurements $$b_i = \langle A_i, X^\star \rangle$$, where an unknown subset of the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the $$A_i$$'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^\star$$. For the closely-related problem of semi-random 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 low-rankness in matrix problems, which may have other applications in obtaining robust algorithms for sparse and low-rank problems.