Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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}$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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