  This paper proposes a fast and accurate method for sparse regression in the
presence of missing data. The underlying statistical model encapsulates the
low-dimensional structure of the incomplete data matrix and the sparsity of the
regression coefficients, and the proposed algorithm jointly learns the
low-dimensional structure of the data and a linear regressor with sparse
coefficients. The proposed stochastic optimization method, Sparse Linear
Regression with Missing Data (SLRM), performs an alternating minimization
procedure and scales well with the problem size. Large deviation inequalities
shed light on the impact of the various problem-dependent parameters on the
expected squared loss of the learned regressor. Extensive simulations on both
synthetic and real datasets show that SLRM performs better than competing
algorithms in a variety of contexts.
