1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ a vector is best correlated with itself. $\endgroup$
    – Turbo
    Feb 17, 2017 at 20:32

1 Answer 1

1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.