  The problem of structured matrix estimation has been studied mostly under
strong noise dependence assumptions. This paper considers a general framework
of noisy low-rank-plus-sparse matrix recovery, where the noise matrix may come
from any joint distribution with arbitrary dependence across entries. We
propose an incoherent-constrained least-square estimator and prove its
tightness both in the sense of deterministic lower bound and matching minimax
risks under various noise distributions. To attain this, we establish a novel
result asserting that the difference between two arbitrary low-rank incoherent
matrices must spread energy out across its entries, in other words cannot be
too sparse, which sheds light on the structure of incoherent low-rank matrices
and may be of independent interest. We then showcase the applications of our
framework to several important statistical machine learning problems. In the
problem of estimating a structured Markov transition kernel, the proposed
method achieves the minimax optimality and the result can be extended to
estimating the conditional mean operator, a crucial component in reinforcement
learning. The applications to multitask regression and structured covariance
estimation are also presented. We propose an alternating minimization algorithm
to approximately solve the potentially hard optimization problem. Numerical
results corroborate the effectiveness of our method which typically converges
in a few steps.
