Why $ \langle \mathcal{R}_{\Omega}\,X\,,\mathcal{R}_{\Omega}\,X\rangle \ge \langle X\,,\mathcal{R}_{\Omega}\,X\rangle $?

Question

Let $\{w_{a}\}_{a=1}^{n^2}$ be an orthonormal basis for a matrix. Assume we pick $m$ elements of this basis uniformly at random. $\Omega$ denotes the set of randomly chosen basis. With that, in matrix completion, the following restriction operator can be defined $$ \mathcal{R}_{\Omega}(X) = \sum_{\alpha\in \Omega} \langle X\,,w_{\alpha} \rangle w_{\alpha} $$ In the paper https://arxiv.org/abs/0910.1879, the following inequality is used $$ \langle \mathcal{R}_{\Omega}\,X\,,\mathcal{R}_{\Omega}\,X\rangle \ge \langle X\,,\mathcal{R}_{\Omega}\,X\rangle $$ If $R_{\Omega}$ is a projection operator, the inequality becomes an equality. In general, I don't know why the inequality holds true. Is there some inequality involving $\langle X\,, \mathcal{A} X\rangle$ and $\langle X\,,\mathcal{A}^{*}\mathcal{A}X\rangle$? I will appreciate any hints or suggestions.

Answer 1

Since I figured this out, I thought I will share it in case somebody runs into the same thing. For an orthonormal basis, this turns out to be actually easy. For general operator basis, things are delicate.

Vectorize $X$ and the basis $w_{\alpha}$ and rewrite the restriction operator as $$ \mathcal{R}_{\Omega}\,x = WW^{T}x $$ where $W$ is a matrix whose columns are the chosen basis vectors. With that, the left side inequality can be written as $$ x^TW(W^{T}W)W^{T}x = \sum_{i} diag(W^TW)_{i} b_i ^{2} $$ where $b = W^{T}x$. Now, if the sampling is with replacement, the matrix $W^TW$ is not identity. But it is a diagonal matrix where the diagonal entries tell us how many times a given basis vector is sampled. Now consider the right hand side of the inequality $$ x^TWW^Tx = \sum_{i} b_i^2 $$ Now comparing the two sides, we see that the left inequality is greater since the diagonals of $W^TW$ are always greater than $1$(by construction). The equality holds if one changes the sampling condition, namely assume that a given basis vector is chosen only once i.e $W^TW=I$