As a part of a series exercises I am doing right now to kill some time during Covid-19 outbreak (and thanks to my University teacher) I stumbled upon this problem:
Let $A:=(A_1|…|A_p)\in \mathbb{R}^{n\times p}$ where horizontal vectors $A_i\in \mathbb{R}^n$ are normalised under $L_2$ norm. Let $b\in col(A)$, where $col(A)$ denotes spaces spanned by columns of matrix $A$, and $\tilde{x}$ be a solution of the linear system $Ax=b$. Let $I$ denote support of $\tilde{x}$, that means indices of rows, where said vector has non-zero values. Let $A_I$ be matrix, consisting of columns $(A_i)_{i\in I}$ and $sign(x_I^*)$ be a vector values given by $sign(x_i^*)$ for any $i\in I$.
By $M(A)$ lets denote $max_{i\neq j}\{|<A_i,A_j>|\}$
The aim is to prove this inequality:
$$||x^*||_0 \leq (1+1/M(A))/2 \implies \forall j \notin I: |A'_JA_I(A'_IA_I)^{-1}sign(x^*_I)|\leq 1$$
Some hints were given as follows:
1) Prove Gershgorin circle theorem for real eigenvalues. (Which I was able to do so)
2) Prove that the largest eigenvalue of $(A'_IA_I)^{-1}$ is smaller than $2/(M(A)+1)$
for which I will present my reasoning and place where I've got stuck:
We know that $(A'_IA_I)^{-1}$ is $n\times n$ matrix, which is positive definite and has real eigenvalues. So from 1) we know that any of its eigenvalues falls into interval given as $[Q_{i,i}-\sum_{j\neq i}|Q_{i,j}|,Q_{i,i}+\sum_{j\neq i}|Q_{i,j}|]$. But we can easly see that $Q_{i,i}=<A_i,A_i>$ is by definition equal to 1, and for other $Q_{i,j}=<A_i,A_j>$. Also we know that $ \forall i,j: |<A_i,A_j>|\leq M(A) $. Also $A'_IA_I$ has only positive eigenvalues and eigenvalues of $(A'_IA_I)^{-1}$ are equal to $1/\lambda$ where $\lambda$ is eigenvalue of $A'_IA_I$. So equivalently we need to find smallest eigenvalue of $A'_IA_I$ and find its lower bound
from 1). But here I've got a problem because I've got such system of inequalities:
$$1-\sum_{j\neq i} |<A_i,A_j>| \leq \lambda \leq 1+\sum_{j\neq i} |<A_i,A_j>|$$ or using $M(A)$
$$1-kM(A) \leq \lambda \leq 1+kM(A)$$
where dimension of $A'_IA_I$ is $k\times k$ from where I can't come to desired form.
3) Use 2) to prove inequality in right hand side of implication.
Here I've also got stuck, as even assuming that 2) is proven, I can't connect how bound on eigenvalue might help me in proving given inequality, using left hand side of implication, no matter how hard I try to wrap my mind around this.
I would appreciate any help, hint or direction to follow in those cases, as I am stuck on them for about 2 days and I am unable to do any progress so far. Thanks in advance!
Best Answer
The original exercise asks us to prove that $$ \|x^*\|_0\leq\frac1{2M}+\frac12\qquad\Longrightarrow\qquad|A_j'A_I(A_I'A_I)^{-1}\mathrm{sign}(x^*)|\leq1. $$ I am going to prove a slightly weaker version of what needs to be proved, namely, the statement that $$ \|x^*\|_0\leq\frac1{2M}\qquad\Longrightarrow\qquad|A_j'A_I(A_I'A_I)^{-1}\mathrm{sign}(x^*)|\leq1. $$ I can't see how to do better than this. Perhaps you will have some idea. Perhaps the fact that $\|x^*\|_0$ must be an integer has something to do with it.
You have proved that $$ \|(A_I'A_I)^{-1}\|\leq\frac1{1-kM}. $$ Now we use $$ k=\|x^*\|_0\leq\frac1{2M}, $$ to infer $$ \|(A_I'A_I)^{-1}\|\leq\frac1{1-kM}\leq2. $$ On the other hand, we have $$ \|A_j'A_I\|_2\leq M\sqrt{k}, \qquad\textrm{and}\qquad \|\mathrm{sign}(x^*)\|_2\leq\sqrt{k}, $$ and hence $$ |A_j'A_I(A_I'A_I)^{-1}\mathrm{sign}(x^*)|\leq\|A_j'A_I\|_2\|(A_I'A_I)^{-1}\|\|\mathrm{sign}(x^*)\|_2\leq2Mk\leq1. $$