0
$\begingroup$

Denote orthonormal basis in $\mathbb{R}^2$: $(\epsilon_1,\epsilon_2)=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ and $A=\begin{pmatrix}1&0&\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\0&1&\frac{\sqrt{2}}{2}&-\frac{\sqrt{2}}{2}\end{pmatrix}$.

Now let frames $(e_1,e_2,e_3,e_4)=(\epsilon_1,\epsilon_2)A$ and its dual $(\tilde{e}_1,\tilde{e}_2,\tilde{e}_3,\tilde{e}_4)=(\epsilon_1,\epsilon_2)B$. For $x=(1,1)^T$, one can decompose and reconstruct $x$ through $\{e_j\}$ and $\{\tilde{e}_j\}$: $x=\sum_{j}\langle x,\tilde{e}_j\rangle e_j=AB^Tx=\sum_j\alpha_j e_j$ The problem is to determine $B$ such that: 1) $\|\alpha\|_2$ is minimized; 2) $\alpha$ has the least non-zero entries.

The first one can be solved by Moore–Penrose pseudoinverse, but I have no idea about P2. Intuitively it appears to be some analogues of Moore–Penrose pseudoinverse but minimizing $L^1$ norm. Can anyone give hints? Thank you.

1 Answers 1

1

OK I think I've got it.

By SVD, $A=U\Sigma V^T= \begin{pmatrix}0&1\\1&0\end{pmatrix} \cdot \begin{pmatrix}\sqrt{2}&0&0&0\\0&\sqrt{2}&0&0\end{pmatrix} \cdot \begin{pmatrix}0 & \frac{1}{\sqrt{2}} & \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{2} & \frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ -\frac{1}{2} & -\frac{1}{2} & \frac{1}{\sqrt{2}} & 0\end{pmatrix}$

Let $\beta=V^T\alpha$, then $\begin{pmatrix}\sqrt{2}&0&0&0\\0&\sqrt{2}&0&0\end{pmatrix} \cdot\begin{pmatrix}\beta_1\\\beta_2\\\beta_3\\\beta_4\end{pmatrix} =\begin{pmatrix}1\\1\end{pmatrix}\qquad\cdots\cdots(*)$

Therefore $\beta_1=\beta_2=\frac{1}{\sqrt{2}}$. Further, $\alpha=V\beta=\left(\frac{1}{2}-\frac{\beta _3}{2}-\frac{\beta _4}{2},\frac{1}{2}+\frac{\beta _3}{2}-\frac{\beta _4}{2},\frac{1}{\sqrt{2}}+\frac{\beta _4}{\sqrt{2}},\frac{\beta _3}{\sqrt{2}}\right)^T$

To achieve sparsity, it must hold that $\beta_3=0$ and $\beta_4=1$, yielding $\alpha=(0,0,\frac{1}{\sqrt{2}},0)^T$

Now from $(*)$ and $AB^T=I$, we have $\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\\0\\1\end{pmatrix} =\begin{pmatrix}\frac{1}{\sqrt{2}}&0\\0&\frac{1}{\sqrt{2}}\\0&0\\0&1\end{pmatrix} \cdot \begin{pmatrix}1\\1\end{pmatrix}=\tilde{B}^T\begin{pmatrix}1\\1\end{pmatrix}$

The entries in lower part of $\tilde{B}^T$ are chosen out of simplicity.

Finally, $B=\left(V\tilde{B}^TU^T\right)^T=\begin{pmatrix} 0 & -\frac{1}{2} & \frac{3}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} \\ 0 & \frac{1}{2} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} \end{pmatrix}$