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

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.

• a vector is best correlated with itself. – T.... Feb 17 '17 at 20:32

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$