Constante de Lipschitz et convolution

NM001 · January 2016

Bonjour,

J'ai un petit problème avec cette fonction :

$x \mapsto \frac{1}{2}\|h*x-b\|^2$ où $h$, $x$ et $b$ sont des matrices.

En effet, je cherche sa constante de Lipschitz, la constante de Lipschitz de la différentielle de cette application mais je ne sais pas comment traiter le produit de convolution… Il faut je pense utiliser la transformée de Fourier Discrète, mais je ne conclus pas.

Welfar · January 2016

C'est pour quelle norme ?

P. · January 2016

Obscur. Pour parler de convolution il faut qu'il s'agisse de fonctions definies sur une espace vectoriel. Je soupconne que l'etoile est un produit ordinaire de matrices. Autres questions, quelles sont les dimensions respectives des matrices $h,x,b?$ et le plus important, quelle norme choisis tu sur les matrices?

NM001 · January 2016

En effet, je n'ai pas été très précis, je vais préciser :

A la base, $h$ est une matrice de petite dimension, mais on la complète avec des 0 pour qu'elle soit de la même taille que $x$ (qu'on a aussi complété avec des 0, pour que convolution linéaire et circulaire coincide). Bien sur, $b$ a la même taille.

Pour la norme, on va dire celle de Frobenius, pour pouvoir utiliser un produit scalaire…

Et l'étoile n'est pas un produit de matrice, mais un produit de convolution en 2d (sinon c'est facile)

gebrane · January 2016

le produit * est pris dans ce sens? https://fr.wikipedia.org/wiki/Filtre_de_Sobel

P. · January 2016

Comprends toujours pas. Convolution en 2d? en deux dimensions? convolution lineaire? circulaire? Le produit cite par gebrane0 est un vulgaire produit de matrices. Ce que tu appelles norme de Frobenius est ce $\|a\|=\sqrt{\mathrm{trace }\, (aa^*)}?$ Donne des definitions completes si tu veux qu'on te reponde.

NM001 · January 2016

Ceux sont des termes qui me parraissaient connus, mais je peux les redéfinir :

Alors la norme de Frobenius c'est bien l'application $A\sqrt{ \mapsto tr(A^*A)}$

Le produit est pris dans ce sens : convolution 2d

il a l'avantage de vérifier (sous certaines hypothèses de remplissement de 0, que j'ai fait ) $A*B = \mathcal{F}^{-1}({\mathcal{F}(A) \times \mathcal{F}(B)})$ où $\times$ est un produit terme à terme, et où $\mathcal{F}$ est la transformée de Fourier Discrète (2D) en ce sens :

P. · January 2016

C'est toujours de l'hebreu. Si $h=(h_{ij})_{1\leq I\leq p,\ 1\leq j\leq q}$ et $x=(x_{k\ell})_{1\leq k\leq n,\ 1\leq \ell\leq m}$ pour quelles valeurs de $p,q,n,m$ le produit $h*x$ est-il defini? et dans ce cas quel est-il?

remarque · January 2016

Il faut sans doute prolonger par $0$ à $\Z^2$. Ceci dit, c'est une fonction quadratique qui tend vers l'infini à l'infini (inutile). Il est peu probable qu'elle soit lipschitzienne.

NM001 · January 2016

Désolé, c'est une erreur de ma part, on veut la constante de Lipschitz de la différentielle de cette fonction. Je corrige sur le post initial. Vraiment désolé.

P. · January 2016

Le procede (que je n'ai toujours pas compris) )$x\mapsto\varphi(x)= h*x$ etant problement lineaire, la norme de la differentielle est deux fois celle de $\varphi.$

NM001 · January 2016

Oui l'idée est là. C'est linéaire, mais on ne peut pas exprimer facilement l'opérateur… Car il me faut la constante de Lipschitz en fonction de $h$, pas de $\varphi$, et je ne vois pas comment faire

P. · January 2016

On en revient au besoin d'une definition de $h*x$ que nous attendons toujours.

remarque · January 2016

SI $H$ désigne l'opérateur $y\mapsto h*y$ (je suppose qu'on se débrouille avec les valeurs au bord pour rester dans le même espace de matrices), alors la constante est la norme subordonnée de $H^TH$. Donc c'est le rayon spectral de $H^TH$, mais ça n'aide pas trop à le calculer explicitement...

P. · January 2016

Je crois qu'l manque une constante a ce que dit Remarque. Formellement je me donne 4 espaces euclidiens E_i. J'appelle $L_{ij}$ l'espace des applications lineaires de $E_i$ dans $ E_j$, je fixe $ g\in L_{12}$ et $h\in L_{34}$ et je me pose le probleme d'evaluer la norme de l'application $\varphi$ de $L_{23}$ dans $L_{14}$ defini par $\varphi(x)=hxg.$ Alors l'adjoint de $\varphi$ est donne par $\varphi^*(y)=h^*yg^*$ si bien qu' on cherche la trace de $\varphi^*\varphi$ defini par $\varphi^*\varphi(x)=h^*hxgg^*.$ Comme les $h^*h$ et $gg^*$ sont diagonalisables en base orthonormale, cela montre que la trace de $\varphi^*\varphi$ est le produit des traces de $h^*h$ et $gg^*.$ Dans le cas de notre ami, $E_1=E_2$ et $g$ est l'identite dont la trace est $ \dim E_2$ . Bref, la norme cherchee est $\sqrt{\dim E_2}\|h\|.$

P. · January 2016

L'emploi du mot matrice dans la discussion fait perdre le nord. En fait on considere deux fonctions $h$ et $x$ sur le groupe $G=\mathbb{Z}^2$ telles que
$h_{k,m}=0$ sauf pour un nombre fini de $(k,m)\in G$ et telles que $x$ soit dans $\ell^2(G)$, c'est a dire que $\|x\|^2=\sum_{(k,m)\in G}x^2_{k,m}<\infty$. On definit $$(h*x)_{k,m}=\sum_{(j,n)\in G}h_{j,n}x_{k-j,m-n}$$ et on se demande quel est le plus petit nombre $A_h$ tel que pour tout $x$ on a
$\|h*x\|\leq A_h\|x\|.$ Pour cela on introduit la transformee de Fourier

$$\mathcal{F}(x)(t,s)=\sum_{(k,m)\in G}x_{k,m}e^{ikt+ims}$$
et on utilise Plancherel qui dit que $$\|x\|^2=\frac{1}{4\pi^2}\int_0^{2\pi}\int_0^{2\pi}|\mathcal{F}(x)(t,s)|^2dtds$$
ainsi que le fait que $$\mathcal{F}(h*x)=\mathcal{F}(h)\mathcal{F}(x)$$
Avec cela il n'est pas difficile de demontrer que $A_h=\max_{(t,s)}|\mathcal{F}(h)(t,s)|.$

remarque · January 2016

@ P. : Où est passée la transposée de la convolution par $h$ ?

Dans le cadre du traitement d'image, il faut quand même gérer le fait que les images sont de taille donnée. J'imagine que l'on prolonge l'image par $0$, par contre, je ne sais pas ce que l'on fait pour le filtre, ça n'a peut-être pas trop d'importance (quoi qu'il doive se passer des choses près du bord de l'image si l'on prolonge par $0$).

NM001 · January 2016

En fait, comme dit remarque dans un post un peu plus haut, si on appelle $H = h*$, trouver la constante de Lipschitz revient à trouver la norme de $H^TH$ et j'y arrive à peu près si tout est des vecteurs…

Pour les valeurs au bord, compléter par des 0 suffit pour enlever les effets de bord.

Par contre je ne comprends pas d'où vient le $\max$ dans le post de P.

Et merci de votre aide sur ce sujet.

P. · January 2016

J'arrete ce dialogue de sourds, ne comprenant ni ce que dit remarque ni ce que dit NM001.

NM001 · January 2016

@P.
Hum… En fait je cherche la constante de la différentielle de $x \mapsto \|Hx-b\|^2$, la constante de Lipschitz de celle-ci est $\||H^T H\||$ sauf que je ne peux pas facilement exprimer $H$ (qui va de $M_n$ dans $M_n$).

J'ai alors deux problèmes.
- Comment exprimer $H^T H$ en fonction de $h$ ?
- Qu'est ce que $ \||.\||$ ? C'est la norme subordonnée à la norme de Frobenius, mais je ne sais pas comment la calculer…

Si je dois changer de norme initiale (prendre la norme subordonnée à la norme euclidienne par exemple), je peux.
J'espère que j'ai été clair

[Inutile de répéter le message précédent. AD]

remarque · January 2016

La norme de Frobenius est juste la norme euclidienne sur l'espace des matrices, pour laquelle les matrices élémentaires sont orthonormées. Comme $H^TH$ est symétrique, sa norme subordonnée est donc son rayon spectral. Maintenant, je n'ai aucune idée de comment calculer ce rayon spectral en fonction de $h$.

Si tu es prêt à changer de norme, les normes 1 ou $\infty$ donnent des normes subordonnées qui sont explicitement calculables en fonction des coefficients. Ca risque de ne pas être très fun, même avec ces choix.

remarque · January 2016

Je détaille peut-être les calculs, parce que en fait, on n'a pas trop le choix de changer de norme. Je note $Hx=h*x$. Si $F$ est la fonction de départ, $DF(x)y=(Hx-b|Hy)$ avec le produit scalaire $(x|y)=\mathrm{tr}\,(x^Ty)$. Donc $(DF(x)-Df(x'))y=(H(x-x')|Hy)=(H^TH(x-x')|y)$. Là, si on change de norme, on ne peut pas utiliser Cauchy-Schwarz, ou alors avec une constante qui risque de pas être optimale. Restons avec la norme de Frobenius
$$\|DF(x)-Df(x')\|=\sup_{\|y\|\le 1}|(DF(x)-Df(x'))y|= \|H^TH(x-x')\|\le \|H^TH\|\|x-x'\|=\rho(H^TH)\|x-x'\|.$$

P. · January 2016

Pour pouvoir continuer a parler, il faudrait que NM001 me dise si j'ai correctement compris dans mon avant dernier message son modele. Si c'est correct, alors mon $A_h$ n'est pas la norme de Frobenius, tres inadaptee ici, mais simplement la norme d'operateur. Si NM001 ne comprend pas d'ou vient $A_h=\max_{s,t}$ cela s'explique ainsi: puisque $g(s,t)=\mathcal{F}(h)(s,t)$ est une fonction continue sur $T=(0,2\pi)^2$ alors $ A_h$ est le plus petit nombre tel que pour tout $f\in L^2(T)$ on a $$\frac{1}{4\pi^2}\int_T |fg|dtds\leq A_h\left(\frac{1}{4\pi^2}\int_T|f|^2dtds\right)^{1/2}$$

Il est clair que $A_h\leq \max|g|=m.$ Pour voir l'egalite, on considere $T_{\epsilon}=\{(s,t)\in T; |g|>m-\epsilon\}$ et $f=1_{T_{\epsilon}}.$ Cela montre que $m-\epsilon\leq A_h$ et montre le resultat.

Exemple $h_{k,m}=1$ si $|k|,|m|\leq 1$ et zero sinon. Alors $A_h=9.$

NM001 · January 2016

Oui P., je pense que tu as bien cerné le problème. Mais tu calcules la norme de $H$ et non pas celle de $H^TH$, a-t-on que cette dernière est égale à la norme de $H$ au carré ?

En fait je ne suis pas sur de tout comprendre… D'après remarque, la norme subordonnée de la norme de Frobenius, est le rayon spectrale, ce qui est plutôt une bonne nouvelle, je pense.

Pourquoi dis tu que la norme n'est pas celle de Frobenius par contre ? J'ai l'impression que ça pourrait l'être, non ? Puisque c'est la norme euclidienne sur l'espace des matrices ?
Et tu parles de norme d'opérateur, mais à propos de quelle norme ? Car H va de $M_n$ dans $M_n$ donc il faut quand même munir $M_n$ d'une norme, tu subordonnes une norme subordonnée ? (je sais vraiment pas)

J'ai l'impression quand même que si on utilise la norme de Frobenius dans notre problème, la constante de la différentielle est $\max \mathcal |{F}(h)|^2, mais j'aimerais bien pouvoir le prouver proprement.

remarque · January 2016

@NM001 : ta fonction de départ est calculée avec la norme de Frobenius au carré. Cette norme est une norme euclidienne. Quand on calcule la différentielle, on voit apparaître naturellement le produit scalaire correspondant. Et l'opérateur $H^TH$ est symétrique pour ce produit scalaire évidemment.

Maintenant, quand tu as une norme euclidienne sur $\R^k$ disons pour concrétiser le truc, $A$ une matrice $k\times k$, et que tu prends la norme euclidienne canonique sur $\R^k$, alors la norme matricielle subordonnée est donnée par $\rho(A^TA)^{1/2}$. Si $A$ est symétrique, ça donne exactement $\rho(A)$. On est dans ce cas de figure ici.

A partir de là, calculer le rayon spectral en trouvant la plus grande valeur propre ne me semble pas aisé. Il y a peut-être un passage par Fourier, puisque $H$ devient un opérateur de multiplication et que $\rho(H^TH)$ est bien la norme matricielle subordonnée de $H$, au carré.

NM001 · January 2016

remarque écrivait:

> @NM001 : ta fonction de départ est calculée avec
> la norme de Frobenius au carré. Cette norme est
> une norme euclidienne. Quand on calcule la
> différentielle, on voit apparaître naturellement
> le produit scalaire correspondant. Et l'opérateur
> $H^TH$ est symétrique pour ce produit scalaire
> évidemment.
>
> Maintenant, quand tu as une norme euclidienne sur
> $\R^k$ disons pour concrétiser le truc, $A$ une
> matrice $k\times k$, et que tu prends la norme
> euclidienne canonique sur $\R^k$, alors la norme
> matricielle subordonnée est donnée par
> $\rho(A^TA)^{1/2}$. Si $A$ est symétrique, ça
> donne exactement $\rho(A)$. On est dans ce cas de
> figure ici.

Alors là juste pour être sur, on cherchait la norme de \||A^TA\||, et c'est la que je comprend plus. C'est $\rho(A^TA)^{1/2}$ ? J'avais cru comprendre que $\rho(A^TA)^{1/2}$ = \||A\||.

> A partir de là, calculer le rayon spectral en
> trouvant la plus grande valeur propre ne me semble
> pas aisé. Il y a peut-être un passage par
> Fourier, puisque $H$ devient un opérateur de
> multiplication et que $\rho(H^TH)$ est bien la
> norme matricielle subordonnée de $H$, au carré.

Je crois que la méthode proposé par P. permet de faire ça… Avec des , je diagonalise justement $H$ par la transformée de Fourier, et ça permet d'avoir cette norme en fonction de la transformée de $h$. Ça ressemble beaucoup, mais je me perd avec toutes ces normes.

Je n'arrive pas à être sur de ces résultats… En tout cas, vraiment désolé pour ma lenteur à comprendre tout ça, et merci encore pour votre aide

remarque · January 2016

NM001 écrivait:

> Alors là juste pour être sur, on cherchait la norme de \||A^TA\||, et c'est la que je comprend plus. C'est $\rho(A^TA)^{1/2}$ ? J'avais cru comprendre que $\rho(A^TA)^{1/2}$ = \||A\||.

Dans cette partie-là, il faut comprendre $A=H^TH$. La norme subordonnée de $H^TH$ est le rayon spectral de $(H^TH)^TH^TH$ à la puissance $1/2$. Comme $H^TH$ est symétrique, $(H^TH)^TH^TH=(H^TH)^2$ et on retombe en fait sur le rayon spectral de $H^TH$.

NM001 · January 2016

Ah bien sur. Donc on cherche le rayon spectrale (la plus grande valeur propre) de $H^TH$. Est ce qu'on a alors $\rho(H^TH) = \rho(H)^2$ ? (en fait je ne suis même pas que ça ait un sens)

Dans ce cas là, en faisant comme proposé par P., on peut avoir $\rho(H) = \max |\mathcal{F}(h)|$ et du coup on aurait le résultat non ?

J'ai l'impression qu'il ne manque plus grand chose

remarque · January 2016

NM001 écrivait:

> Est ce qu'on a alors $\rho(H^TH) = \rho(H)^2$ ? (en fait je ne suis même pas que ça ait un sens)

Ca a un sens, mais c'est faux. Exemple $\begin{pmatrix}0&1\\0&0\end{pmatrix}$. C'est vrai si $H$ est symétrique et plus généralement normale.

> Dans ce cas là, en faisant comme proposé par P.,on peut avoir $\rho(H) = \max |\mathcal{F}(h)|$ et du coup on aurait le résultat non ?

Je n'ai pas regardé le détail des calculs de P., mais c'est bien possible. Ceci dit, la max d'une transformée de Fourier n'est pas spécialement plus accessible qu'une plus grande valeur propre...

NM001 · January 2016

remarque écrivait:

> NM001 écrivait:
>

>

> > Est ce qu'on a alors $\rho(H^TH) = \rho(H)^2$ ?
> (en fait je ne suis même pas que ça ait un
> sens)
>
> Ca a un sens, mais c'est faux. Exemple
> $\begin{pmatrix}0&1\\0&0\end{pmatrix}$. C'est vrai
> si $H$ est symétrique et plus généralement
> normale.

Ah oui, je comprend. Mais l'opérateur associé à la convolution, $H$, j'ai du mal à me le représenter, mais il n'est pas symétrique, si ?

> > Dans ce cas là, en faisant comme proposé par
> P.,on peut avoir $\rho(H) = \max |\mathcal{F}(h)|$
> et du coup on aurait le résultat non ?
>
> Je n'ai pas regardé le détail des calculs de P.,
> mais c'est bien possible. Ceci dit, la max d'une
> transformée de Fourier n'est pas spécialement
> plus accessible qu'une plus grande valeur
> propre...

Mais visiblement, d'un côté, on parle de $H$ et de l'autre de $h$, c'est pour ça que ça me parait pratique.

remarque · January 2016

NM001 écrivait:

> Mais l'opérateur associé à la convolution, $H$, mais il n'est pas symétrique, si ?

J'ai un peu la flemme, mais il suffit de l'écrire dans la base canonique pour voir s'il l'est ou pas. A priori, je ne vois pas de raison pour, mais sait-on jamais.

> Mais visiblement, d'un côté, on parle de $H$ et de l'autre de $h$, c'est pour ça que ça me parait pratique.

D'un côté, on parle de $H$ qui est intimement lié à $h$ par $Hx=h*x$ et de l'autre on parle de $\mathcal{F}(h)$ qui est intimement lié à $h$ par la transformation de Fourier. Dans aucun des deux cas, on n'a quelque chose de directement explicitable en fonction des coefficients de $h$ (sauf si quelqu'un trouve que c'est en fait explicite). Bonnet blanc, blanc bonnet. Tout dépend de ce que tu veux en faire après.

P. · January 2016

L'adjoint de $x\mapsto h*x$ est $x\mapsto \tilde{h}*x$ avec $ \tilde{h}_{k,m}=h_{-k,-m}.$

Constante de Lipschitz et convolution

Réponses

Bonjour!

Catégories

In this Discussion