théorème de Candès sur le compressed sensing

Fabrice2
Fabrice2
dans Analyse
Bonjour,

Je cherche à reprendre une démonstration dans l'article de Candès : The Restricted Isometry Property and Its Implications for Compressed Sensing.

A à une certaine étape, on a un vecteur $h \in \R^n$ et on considère deux sous-ensembles disjoints $T_0$ et $T_1$ de $\{1,...,n\}$.
On note $h_{T_0}$ le vecteur tel que $(h_{T_0})_i = h_i, \forall i \in T_0$ et $(h_{T_0})_i = 0, \forall i \notin T_0$
De même pour $h_{T_1}$.

Et je cherche donc à retrouver cette inégalité :
${\left\Vert h_{T_0} \right\Vert} + {\left\Vert h_{T_1} \right\Vert} \leq \sqrt{2} {\left\Vert h_{T_0 \cup T_1} \right\Vert}$
où la norme utilisée ici la norme euclidienne l2.

J'ai écrit $h_{T_0 \cup T_1} = h_{T_0} + h_{T_1} $ puis développé le carré de la norme en utilisant que le produit scalaire entre $h_{T_0}$ et $h_{T_1}$ est nul car les deux supports sont disjoints, mais je n'aboutis pas. Pouvez-vous m'éclairer ? Merci.

Réponses

  • Foys
    Foys
    $h_{T_0}$ et $h_{T_1}$ sont orthogonaux vu que $T_0 \cap T_1=\emptyset$. Donc $||h_{T_0}+h_{T_1}||^2=||h_{T_0}||^2+||h_{T_1}||^2$, on conclut avec l'inégalité $(a+b)^2=2a^2+2b^2-(a-b)^2 \leq 2a^2+2b^2$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Raymond Cordier
    Raymond Cordier
    Comme $T_{0}$ et $T_{1}$ sont disjoints, on a : $\left\| h_{T_{0}}\right\| ^{2}+\left\| h_{T_{1}}\right\| ^{2}=\left\| h_{T_{0}\cup T_{1}}\right\| ^{2}$, et l'inégalité demandée provient de celle-ci : $(a+b)^{2}\leq 2(a^{2}+b^{2}) $.
    Peut-on télécharger cet article ?
    Bonne soirée.
    RC
  • Raymond Cordier
    Raymond Cordier
    Je n'avais pas vu la réponse précédente ...
  • Kuja
    Kuja
    Et voilà l'article en PJ. Toujours aussi balèze ...

    Amicalement,
  • Fabrice2
    Fabrice2
    Un grand merci ! J'en profite pour poser deux autres questions :

    Plus loin dans l'article que du coup j'ai mis en pièce jointe, j'ai essayé de retrouver les deux formules successives (un peu avant le lemme 2.2) :

    ${\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} \leq \alpha \epsilon + \rho s^{-1/2} {\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} + 2 \rho e_0$

    qui entraine ${\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} \leq (1-\rho)^{-1} ( \alpha \epsilon + 2 \rho e_0)$

    Déjà pour la première formule, j'utilise (14) et (12), qui me donnent :
    ${\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} \leq \alpha \epsilon + \rho s^{-1/2} {\left\Vert h_{T_0} \right\Vert}_{l_1} + 2 \rho s^{-1/2} \left\Vert x_{T_0^c} \right\Vert}_{l_1} $

    Or $x_{T_0^c} = x - x_s$ et $e_0 = s^{-1/2} \left\Vert x - x_s \right\Vert}_{l_1} $
    De plus $s^{-1/2} \left\Vert h_{T_0} \right\Vert}_{l_1} \leq \left\Vert h_{T_0} \right\Vert}_{l_2} $ par Cauchy-Schwartz

    et je trouve donc ${\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} \leq \alpha \epsilon + \rho s^{-1/2} {\left\Vert h_{T_0} \right\Vert}_{l_2} + 2 \rho e_0$ au lieu de la formule attendue, qui du reste n'est pas fausse puisqu'on a naturellement
    ${\left\Vert h_{T_0} \right\Vert}_{l_2} \leq {\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2}$. Mais ça peut etre gênant pour la suite. Qu'en pensez-vous ?

    Ensuite, pour la deuxième formule attendue, je pars de la première pour arriver à :
    ${\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} \leq \alpha \epsilon + \rho {\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2} + 2 \rho e_0 = (\alpha \epsilon + 2 \rho e_0)(1+\rho \frac{ {\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2}}{\alpha \epsilon + 2 \rho e_0})$

    Et là pour aboutir au résultat souhaité, je dois montrer que $\frac{ {\left\Vert h_{T_0 \cup T_1} \right\Vert}_{l_2}}{\alpha \epsilon + 2 \rho e_0} \leq 1$, mais je n'y parviens pas. Pouvez-vous m'aider ? Merci.


    RIP.pdf 155.3K
  • Fabrice2
    Fabrice2
    Encore une question du même genre et ce sera la dernière, si je n'ose abuser de votre patience :

    A la fin de l'article, je souhaite retrouver la formule :
    $\left\Vert h_{T_0^c} \right\Vert}_{l_1} \leq 2(1-\rho)^{-1} \left\Vert x_{T_0^c} \right\Vert}_{l_1}$

    Pour cela, j'utilise (12) et (15) qui me donnent :
    $ \left\Vert h_{T_0^c} \right\Vert}_{l_1} \leq \rho \left\Vert h_{T_0^c} \right\Vert}_{l_1} + 2 \left\Vert x_{T_0^c} \right\Vert}_{l_1} = 2 \left\Vert x_{T_0^c} \right\Vert}_{l_1} (1 + \rho \frac{ {\left\Vert h_{T_0^c} \right\Vert}_{l_1} }{ 2 {\left\Vert x_{T_0^c} \right\Vert}_{l_1} })$

    Du coup, il reste à montrer que $\frac{ {\left\Vert h_{T_0^c} \right\Vert}_{l_1} }{ 2 {\left\Vert x_{T_0^c} \right\Vert}_{l_1} } \leq 1$ , ce qui semble assez évident vu que $h$ est l'erreur d'approximation de $x$ par $x^{*}$. Mais quand même, voyez-vous une justification plus rigoureuse ? Merci pour votre aide, surtout pour la première majoration par 1 !
  • Fabrice2
    Fabrice2
    Bonjour,
    personne pour m'éclairer un peu ?
    merci
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français