  We consider the problem of recovering an unknown effectively
$(s_1,s_2)$-sparse low-rank-$R$ matrix $X$ with possibly non-orthogonal
rank-$1$ decomposition from incomplete and inaccurate linear measurements of
the form $y = \mathcal A (X) + \eta$, where $\eta$ is an ineliminable noise. We
first derive an optimization formulation for matrix recovery under the
considered model and propose a novel algorithm, called Alternating Tikhonov
regularization and Lasso (A-T-LA$\text{S}_{2,1}$), to solve it. The algorithm
is based on a multi-penalty regularization, which is able to leverage both
structures (low-rankness and sparsity) simultaneously. The algorithm is a fast
first order method, and straightforward to implement. We prove global
convergence for any linear measurement model to stationary points and local
convergence to global minimizers. By adapting the concept of restricted
isometry property from compressed sensing to our novel model class, we prove
error bounds between global minimizers and ground truth, up to noise level,
from a number of subgaussian measurements scaling as $R(s_1+s_2)$, up to
log-factors in the dimension, and relative-to-diameter distortion. Simulation
results demonstrate both the accuracy and efficacy of the algorithm, as well as
its superiority to the state-of-the-art algorithms in strong noise regimes and
for matrices, whose singular vectors do not possess exact (joint-) sparse
support.
