Partial Constraint of Low Rank Matrix

Question

Suppose $X \in \mathbb{R}^{m \times n}$ is a rank $r$ matrix. Let $\Omega$ be a generic subset of $\in \{1, \ldots, m\} \times \{1, \ldots, n\}$ of cardinality $r(m + n - r)$. Denote by $X_{\Omega}$ the matrix that is equal to $X$ on $\Omega$, and 0 on $\Omega^\complement$. Putting it mathematically, $$X_{\Omega}(i, j) = \begin{cases} X(i, j), \quad & (i, j) \in \Omega\\ 0, \quad & (i, j) \notin \Omega \end{cases}$$

Then, I was wondering that could we prove that $$\|X - Y\|_{\mathrm{F}} \lesssim \|X_{\Omega} - Y_{\Omega}\|_{\mathrm{F}}$$ for any rank $r$ matrices $X$ and $Y$. Any comments related and literature are very welcome.

Answer 1

The answer is no. Try with $2\times 2$ diagonals!

However, the opposite direction does hold true, because $X_{\Omega}$ is a projection of $X$, so treating $X$ and $Y$ as vectors, and using non-expansivity of projections, we obtain that \begin{equation*} \|P_\Omega(X)-P_\Omega(Y)\| = \|X_\Omega-Y_\Omega\| \le \|X-Y\|, \end{equation*} where $P_\Omega$ is the projection onto the indices given by $\Omega$.

Presumably, you are looking for a reverse inequality with some constants? But as you can easily construct, we may have that $X_\Omega=Y_\Omega$ but $X \neq Y$, in which case the inequality you postulate cannot hold with a nonzero constant factor.