I'm supposed to prove the following:
For two orthonormal bases $\Psi = (\psi_k)_{k = 1}^m$ and $\Phi = (\phi_k)_{k = 1}^m$ of $\mathbb R^m$ with mutual coherence $$\mu ([ \Psi \vert \Phi ]) = \max \left\lbrace \frac{\vert \langle u, v \rangle \vert}{\| u \|_2 \| v \|_2} : u, v \in \Psi \cup \Phi , u \neq u \right\rbrace ,$$ and two representations $\alpha, \beta$ of a vector $b \in \mathbb R^m$ with respect to $\Psi, \Phi$, the numbers of non-zero entries fulfill: $$\| \alpha \|_0 + \| \beta \|_0 \geq \frac{2 }{\mu ([\Psi, \Phi ])} .$$
I have no idea where to start or what to do. For the sake of intuition, I thought that if $\mu$ is small, that means that every basis vector $\phi_k$ must have a certain number of components w.r.t. $\Psi$. More precisely, introducing the angles $\cos \theta_{i,k} = \langle \psi_i, \phi_k \rangle ,$ we know that $$ \sum_{i = 1}^m \cos^2 \theta_{i,k} = \sum_{i = 1}^m \cos^2 \theta_{k,i} = 1 \quad (\forall k).$$ On the other hand, if $\mu \leq 1 / \sqrt M, M \in \mathbb N,$ then we know that $\forall k$ there must be at least $M$ indices $i$ such that $\cos \theta_{i,k}\neq 0$.
If there is only one non-zero component in $\alpha$, I hence know that there are at least $M$ non-zero components in $\beta$, so $$\| \alpha \|_0 + \| \beta \|_0 \geq 1 + 1/\mu^2 \geq 2 / \mu,$$ the latter follows from $2 \mu \leq 1 + \mu^2$.
Can I perhaps turn this into an induction proof?
I am also aware of the bound (Welch bound) $\mu (A) \geq \sqrt{(n - m) / ((n-1)m)}$ for any full-rank $m \times n$ matrix, $n > m$. I thought maybe I can use this by extracting some submatrix of the change of basis matrix for $\Psi \to \Phi$, but I don't see how... Of course it would be nice if I could simply take the $\| \alpha \|_0 \times \| \beta \|_0$-submatrix, because then I would (almost) get that the geometric mean of $\| \alpha \|_0$ and $\| \beta \|_0$ is larger than $1 / \mu$, and hence also the arithmetic mean, which is exactly what I want. But I don't see how I can conclude that... (EDIT: This is of course not correct anyway, since the mutual coherence of the change of basis matrix is not the same as the mutual coherence of the "pasted basis matrix"...)
I'm grateful for any idea.
The proof is actually quite simple. It is given in "Sparse and Redundant Representations" by M. Elad (https://link.springer.com/book/10.1007/978-1-4419-7011-4), Theorem 2.1. The idea (for the alternative proof due to Pinkus mentioned in the book) is to bound $\vert \beta_i \vert^2 \leq \| b \|_2^2\, \| \alpha \|_0\, \mu([\Psi, \Phi])^2$ (this is straight-forward), which implies $\| \beta \|_2^2 \leq \| \beta \|_2^2\, \| \alpha \|_0 \,\| \beta \|_0 \,\mu ([ \Psi , \Phi ])^2$. Now cancel out the norm of $\beta$ and use AGM inequality.