Matrix Estimation with Adjustable Sampling Rate
Here’s a very interesting matrix completion method and result, which is a direct corollary from Koltchinskii, Lounici and Tsybakov (2011) paper. Consider the following matrix estimation problem: for input matrix $A\in \mathbb R^{m_1\times m_2}$, assume $m_1 < m_2$ and $\text{rank}(A) = r \ll m_2$. $n$ entries of $A$ are observed at uniformly at random, with independent noise $\epsilon_{ij}$. Denote as $\Omega$ the index set of observed entries of $A$, define the scaled observation matrix $Y = [y_{ij}]$ as $$ y_{ij} = \frac{m_1 m_2}n \begin{cases} a_{ij} +\epsilon_{ij} & (i, j) \in \Omega\cr 0 & (i, j)\notin \Omega \end{cases},\quad (i, j)\in [m_1]\times [m_2]....
