Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.