3
$\begingroup$

Let $A \in \mathbb{R}^{m \times n}$.

Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to

$\min \limits_{x \text{ s.t.} Ax=y} |x|_1$ for any $y$.

If yes, where can I read about this result. I am not 100% sure that I have got the criteria correctly.

Update. $|M|_{\infty} = \max \limits_{i,j} |M_{ij}|$

Improve this question
$\endgroup$
6
  • $\begingroup$ Do $Q,A$ have any useful property? $\endgroup$
    – Turbo
    Commented Jun 24, 2019 at 15:31
  • $\begingroup$ No. I was hoping for someone to recognize this fact and point me towards a reference. $\endgroup$
    – love_backups
    Commented Jun 24, 2019 at 15:55
  • $\begingroup$ They wont do that here unless you define everything precisely. $\endgroup$
    – Turbo
    Commented Jun 24, 2019 at 15:58
  • $\begingroup$ I have provided as much information as I could. $\endgroup$
    – love_backups
    Commented Jun 24, 2019 at 16:22
  • 1
    $\begingroup$ Could you check the sized of A and Q? Right now the product QA is not defined. Also, do you want $n\geq m$? Should A have full rank? (I guess you need both since otherwise, the minimization problem may be infeasible.) $\endgroup$
    – Dirk
    Commented Jun 24, 2019 at 20:06

1 Answer 1

Reset to default
3
$\begingroup$

Yes, this is true. Since there exists a 'decoder' $Q$ which gives a value on the right hand side (close to or equal to) $\frac{1}{2}$, the pair $(A,Q)$ are $(\ell_\infty, \ell_1)$-instance optimal (see this talk of Foucart, pg 75, for details). From this it follows that no non-trivial $2$-sparse vectors lie in the kernel of $A$ and that $A$ satisfies the null space property of order $2$ for recovery via $\ell_1$-minimization.

Chapter 11 of Foucart's book is another reference for this topic.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see how to relate $||I - QA||_\infty$ and $\max \limits_{x \in \mathbb{R}^n}||x - QAx||_1$. $\endgroup$
    – love_backups
    Commented Jun 25, 2019 at 15:22
  • $\begingroup$ Isn't it $||D^Tx||_1 \leq \sum\limits_{i = 1}^n ||d_i^T x||_\infty ||x||_1 \leq n \max|d_{ij}| ||x||_1$. That is, we cannot bound by $\max |(I - QA)|_{j,k}$ alone. Or are you using some kind of generalized H\"olders inequality? $\endgroup$
    – love_backups
    Commented Jun 25, 2019 at 16:40
  • $\begingroup$ @love_backups It should be $\|\cdot\|_{\infty}$ above. This has been updated. $\endgroup$
    – Josiah Park
    Commented Jun 25, 2019 at 21:20
  • $\begingroup$ Could you please elaborate on your answer? Specifically, I do not see the link between what I have written in the question and what is written on the page 75 in the Foucart's talk. $\endgroup$
    – love_backups
    Commented Jun 26, 2019 at 11:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .