\documentclass[12pt]{article}\usepackage[francais]{babel}
\usepackage{amssymb,amsmath}\usepackage[ansinew]{inputenc}
\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{3cm}
\addtolength{\hoffset}{-1.5cm}
\newtheorem{lemme}{Lemme}
\newtheorem{theo}[lemme]{Th\'eor\`eme}
\newtheorem{ex}[lemme]{Exemple}
\newtheorem{cor}[lemme]{Corollaire}
\newtheorem{prop}[lemme]{Proposition}
\newtheorem{rem}[lemme]{Remarque}
\newtheorem{defi}[lemme]{D\'efinition}
\newenvironment{pf}{\begin{trivlist}\item[]{\bf Preuve}}
{\mbox{}\hfill\rule{.08in}{.08in}\end{trivlist}}
\def\n#1{\parallel #1\parallel}
\def\f{\mathbb{F}_p}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\d{\displaystyle}

\begin{document}
\title{Reconstruction creuse d\'eterministe, d'apr\`es  Guruswami, Lee et Razborov}
\author{Pierre Pansu}
\maketitle
\section{Objectif}

Exposer bri\`evement des r\'esultats r\'ecents, trouv\'es dans la litt\'erature informatique, qui utilisent l'estim\'ee somme-produit de Bourgain, Katz et Tao.

Aujourd'hui, c'est une construction explicite de sous-espaces dont l'intersection avec la boule unit\'e de $\ell^1$ est presque ronde, par Guruswami, Lee et Razborov. 


\section{Distorsion des sous-espaces}

\subsection{Compression}

En compression, la m\'ethode suivante est \`a la mode, depuis les travaux de Candes/Tao et Donoho (voir \cite{KT}). Il s'agit de coder des vecteurs $u\in\R^N$, en faisant l'hypoth\`ese qu'ils sont $k$-creux, i.e. que seules $k$ composantes du vecteur sont non nulles (e.g., on a décomposé un signal dans une base d'ondelettes, et on n'a conservé que les $k$ composantes de plus grande intensité). On parvient \`a construire des matrices $\Phi:\R^N \to \R^n$, $n\ll N$, qui ont la propri\'et\'e suivante. Si on minimise la norme $\ell^1$ des vecteurs $v$ tels que $\Phi(v)=\Phi(u)$, on retombe forc\'ement sur $u$. On dispose d'un algorithme polyn\^omial pour reconstruire $u$ \`a partir de $\Phi(u)$, on peut donc coder $u$ par $\Phi(u)$ qui est beaucoup plus petit.

La raison g\'eom\'etrique tr\`es grossi\`ere est que les vecteurs creux sont dans
des coins tr\`es aigus de la boule $\ell^1$. Un sous-espace affine qui
contient un tel point a toutes les chances de toucher la boule $\ell^1$ en
ce point. Donoho, puis Candes et Tao, ont d\'egag\'e des conditions
suffisantes sur le noyau de $\Phi$, qui prennent la forme de comparaisons entre normes $\ell^1$ et $\ell^2$ des projections des vecteurs du noyau sur des paquets de coordonn\'ees. Kashin et Temlyakov ont notablement simplifi\'e ces conditions, en \'eliminant les projections sur des paquets de coordonn\'ees.

\begin{defi}
La {\em distorsion} d'un sous-espace vectoriel $X\subset\R^N$ est
\begin{eqnarray*}
\Delta(X)=\sqrt{N}\max_{x\in X}\frac{|x|_2}{|x|_1}.
\end{eqnarray*}
\end{defi}

\begin{ex}
La distorsion est au plus \'egale \`a $\sqrt{N}$, avec \'egalit\'e (entre autres) pour l'espace $\R^N$ entier. 
\end{ex}
Les sous-espaces favorables \`a la reconnaissance des vecteurs creux sont
ceux dont la distorsion est nettement inf\'erieure \`a $\sqrt{N}$.



\begin{lemme}
\label{kt}
{\em \cite{KT}}. Soit $X\subset\R^N$ un sous-espace tel que $\Delta(X)\leq D$. Alors $X$ reconstruit uniquement les vecteurs $k$-creux pour $\d k=\frac{N}{4D^2}$.
\end{lemme}

\begin{pf}
Etant donné $S\subset\{1,\ldots,n\}$, on note $x_S$ le vecteur tronqué dans
lequel on a mis à zéro les coordonnées de $x$ d'indices n'appartenant pas à
$S$.

1. Si $Ax=0$, alors pour tout $S$ de taille inférieure à $\d
k=\frac{N}{4D^2}$, $\n{x_S}_1 \leq \frac{1}{2}\n{x}_1$. En effet, par
Cauchy-Schwarz, 
$$
\n{x_S}_1 \leq \sqrt{|S|}\n{x_S}_2 \leq \sqrt{|S|}\n{x}_2\leq
\frac{\sqrt{N}}{2D}\frac{D}{\sqrt{N}}\n{x}_1 .
$$
2. Si $u$ est $k$-creux et si $Av=Au$, alors $\n{v}_1 > \n{u}_1$. En effet,
   si $S$ est le support de $u$, et si $x=v-u$,
\begin{eqnarray*}
\n{v}_1 &=&\n{u+x}_1 = \n{(u+x)_S}_1 +\n{x_{\bar{S}}}_1 \\
&\geq& \n{u_S}_1 -\n{x_S}_1 +\n{x_{\bar{S}}}_1 \\
&=&\n{u}_1 +\n{x}_1 -2\n{x_{\bar{S}}}_1 \\
&\geq& \n{u}_1.
\end{eqnarray*}

\end{pf}

Il s'agit donc de construire des sous-espaces de distorsion la plus petite possible.


\subsection{Résultats}

Un sous-espace choisi au hasard est ce qui se fait de mieux.

\begin{rem}
Le th\'eor\`eme de Dvoretzky affirme que dans tout espace de Banach de
dimension $N$, il existe un sous-espace vectoriel de dimension $\d k=const(\delta)\frac{\log(k)}{k}$
tel que la norme induite soit \`a distance (de Banach-Mazur) au plus
$1+\delta$ d'un espace euclidien. Ici, on se pose une question
differente, car il s'agit de comparer directement des normes, et non des
normes \`a changement de coordonn\'ees lin\'eaire pr\`es. Néanmoins, on
trouve quand même des sous-espaces de distorsion proche de 1. Comme il ne s'agit pas de n'importe quelle norme, mais de la norme $\ell_1$, les sections presque euclidiennes ont des dimensions linéaires en $N$.
\end{rem}

\begin{theo}
\label{flm}
{\em \cite{FLM}}. Pour tout $\delta>0$, il existe $c_\delta$ tel que si
$c_\delta N$ vecteurs sont tir\'es au hasard dans $S^{N-1}$ et engendrent un
sous-espace $X$, alors avec probabilit\'e tendant vers 1 quand $N$ tend vers l'infini, 
\begin{eqnarray*}
\Delta(X)\leq 1+\delta.
\end{eqnarray*}
\end{theo}

L'énoncé suivant couvre un spectre plus large de situations.

\begin{theo}
\label{random}
{\em \cite{K}, \cite{GG}}. Soit $A$ une matrice de taille $n\times N$ dont les coefficients sont tir\'es au hasard dans $\{\pm1\}$. Avec probabilit\'e tendant vers 1 quand $N$ et $n$ tendent vers l'infini, 
\begin{eqnarray*}
\Delta(\mathrm{ker}A)\leq \sqrt{\frac{N}{n}(1+\log(\frac{N}{n}))}.
\end{eqnarray*}
\end{theo}
Par cons\'equent, les sous-espaces tir\'es au hasard reconstruisent
uniquement les vecteurs $k$-creux pour $\d k=\frac{n}{4\log(N/n)}$.

On voudrait éliminer le hasard. Un gadget favori en combinatoire, les
matrices d'Hadamard, semble un bon candidat. Malheureusement, la matrice
formée des $N/2$ premières lignes d'une matrice d'Hadamard a un noyau dont la distorsion est en $N^{1/4}$.

\medskip

Le th\'eor\`eme expos\'e aujourd'hui fournit de fa\c con d\'etermi\-niste des sous-espaces satisfaisants lorsque le rapport $N/n$ tend vers l'infini assez lentement.

\begin{theo}
\label{glr}
{\em \cite{GLR}}. Pour toute fonction positive $N\mapsto \eta(N)$, il existe un algorithme d\'etermi\-niste qui produit, en un temps polyn\^omial, des sous-espaces vectoriels $X\subset \R^N$ de dimensions $\geq (1-\eta)N$ et de distorsions 
\begin{eqnarray*}
\Delta(X)\leq (\eta^{-1}\log\log N)^{C\log\log N}.
\end{eqnarray*}
\end{theo}

Lorsque $N/n$ cro\^{\i}t comme une puissance de $\log N$, la distorsion obtenue est de la forme $(\frac{N}{n}(1+\log(\frac{N}{n})))^{C\log\log N}$, ce qui est moins bon que le tirage al\'eatoire, mais permet tout de m\^eme de reconstruire les vecteurs $k$-creux avec $\d k=N/(\log N)^{C\log\log\log(N)}$.

\section{Stratégie}

Etant donné un sous-espace vectoriel $L$ de $\R^d$ et un graphe biparti $G$ qui possède $N$ sommets de gauche, et dont tous les sommets de droite sont de même degré $d$, considérons le sous-espace $X(G,L)$ de $\R^N$ formé des vecteurs dont la restriction aux premiers voisins de chaque sommet de droite appartient à $L$. Si le graphe $G$ a un bon profil asymétrique (e.g. linéaire), alors $X(G,L)$ a une faible distorsion. Les graphes aléatoires ont un profil linéaire, mais aucun graphe explicite (et constructible en un temps polynômial en $N$) n'a un aussi bon profil. L'estimée somme-produit garantit que le graphe $ab+c$ a un profil suffisant pour les sous-ensembles de petite taille. Pour les grandes tailles, il vaut mieux utiliser les graphes de Ramanujan (\cite{LPS}).

\section{Profil des graphes bipartis}

\subsection{Définition}

Un graphe biparti a son ensemble de sommets divis\'e en deux parties $V_L$ et $V_R$, les sommets de gauche et ceux de droite. Un sous-ensemble $S\subset V_L$ a un bord $\partial S$ contenu dans $V_R$, c'est l'ensemble des voisins des \'el\'ements de $S$.

\begin{defi}
Le {\em profil asym\'etrique} d'un graphe biparti est la fonction qui \`a un entier $m$ associe $\Lambda(m)$, le minimum des tailles des bords des sous-ensembles de $V_L$ de taille au moins $m$.
\end{defi}

\begin{ex}
Pour le graphe biparti complet, alors $\Lambda(m)=|V_R|$ d\`es que $m>0$.
\end{ex}

\begin{ex}
Pour le graphe biparti al\'eatoire de degr\'e $d$, $\Lambda(m)=c(d)m$.
\end{ex}

\subsection{Graphes d'incidence des graphes de Ramanujan}

Ce qui vient en premier à l'esprit, c'est d'utiliser les graphes de Ramanujan, graphes régulier de petit $\lambda_2$ construits dans \cite{LPS}. On les transforme en graphes bipartis en prenant leurs graphes d'incidence.

\begin{defi}
Soit $\Gamma$ un graphe. Son {\em graphe d'incidence} est le graphe biparti dont les sommets gauche sont les arêtes de $\Gamma$, les sommets droits les sommets de $\Gamma$, et on relie chaque arête à ses extrémités.
\end{defi}

\begin{prop}
\label{ac}
Les graphes d'incidence des graphes de Ramanujan permettent d'obtenir, pour tout $d\geq 5$ et tout $N\geq d$ un graphe à $N$ sommets gauche, $n$ sommets droits, de degré gauche égal à 2, de degré droit égal à $d$, et de profil asym\'etrique $\d\Lambda(m)\geq\min\{\frac{m}{2\sqrt{d}},\frac{2mN}{d}\}$.
\end{prop}

\begin{pf}
Le lien entre $\lambda_2$ et $\Gamma$ et profil du graphe d'incidence provient d'une majoration du nombre d'arêtes des sous-graphes des expanseurs, due à N. Alon et F.R.K. Chung, \cite{AC}. Cette estimation conduit à une perte : le profil n'est pas linéaire pour $m$ petit.
\end{pf}

C'est pour compenser cette faiblesse des graphes d'incidence qu'on utilise les graphes somme-produit.

\subsection{Graphes somme-produit}

\begin{theo}
\label{bkssw}
{\em \cite{GLR}, interpr\'etation de \cite{BKSSW}}. Il existe une constante absolue $\epsilon>0$ telle que, pour tout premier $p$, le graphe biparti tel que
\begin{eqnarray*}
V_L =\f^3 ,\quad V_R =\{1,\,2,\,3,\,4\}\times \f ,
\end{eqnarray*}
et où $(a,b,c)\in \f^3$ est reli\'e \`a $(1,a)$, $(2,b)$, $(3,c)$ et $(4,ab+c)$, a un profil asym\'etrique $\Lambda(m)\geq\min\{p^{0.9},m^{1/3+\epsilon}\}$.
\end{theo}

\begin{rem}
Trivialement, si $S\subset V_L$, $|\partial S|\geq|S|^{1/3}$. 
\end{rem}
En effet, si $S_1 =\{(1,a)\,|;\,(a,b,c)\in S\}$, etc..., alors $S\to S_1 \times S_2 \times S_3$, $(a,b,c)\mapsto((1,a),(2,b),(3,c))$ est injective, donc $|S|\leq |S_ 1 |\times|S_2 |\times|S_3 |$, d'où $|\partial S|\geq |S_ 1 |+|S_2 |+|S_3 |\geq |S|^{1/3}$.

Autrement dit, l'estim\'ee somme-produit permet d'am\'eliorer un petit peu cette in\'egalit\'e triviale, de fa\c con uniforme en $p$.

Ce profil peut paraître très mauvais (bien moins que linéaire). Attention, le nombre de sommets de gauche est le cube du nombre de sommets de droite, $|V_L|=|V_R|^3$, donc il y a forcément peu de premiers voisins. En revanche, il y a beaucoup de seconds voisins, ce qui donne la propriété d'expansion souhaitée.

\begin{pf}
Soit $S\subset V_L =\f^3$. De deux choses l'une.
\begin{itemize}
  \item Ou bien l'une des coordonnées a une influence prépondérante dans $S$ (i.e. $S$ contient un gros sous-ensemble proche d'un produit $A\times\{b\}\times\{c\}$). Dans ce cas, le sous-ensemble $Ab+c\subset\f=V_R$ est contenu dans le bord de $S$, et $|Ab+c|=|A|$ est de l'ordre de $|S|$.
  \item Ou bien les trois coordonnées jouent des rôles équivalents. Dans ce cas, $S$ contient un gros sous-ensemble proche d'un produit $A\times B\times C$. Le sous-ensemble $AB+C\subset\f=V_R$ est contenu dans le bord de $S$, et $|AB+C|>|A|^{1+\epsilon}>|S|^{1/3\,+\epsilon}$, d'après l'estimée somme-produit, à condition que $|A|<|\f|^{1-\epsilon}$.
\end{itemize}
En fait, on a besoin de la version mesures de l'estimée somme-produit, qui apparaît initialement dans \cite{BIW}.
\end{pf}


\section{M\'ecanisme am\'eliorant la distorsion}

Voici une formulation technique de la distorsion.

\begin{defi}
Un sous-espace vectoriel de $\R^d$ est {\em  $(t,T,\epsilon)$-\'etal\'e} si tout vecteur de $X$ satisfait
\begin{eqnarray*}
\min_{S\,;\,|S|\leq T}|x_{\bar{S}}|_2 \geq\epsilon\min_{S\,;\,|S|\leq t}|x_{\bar{S}}|_2 
\end{eqnarray*}
\end{defi}

On montre ais\'ement qu'un espace $(T,t,\epsilon)$-\'etal\'e a une distorsion petite.

\begin{lemme}
Soit $L$ un sous-espace vectoriel de $\R^d$ qui est $(0,t,\epsilon)$-\'etal\'e. Soit $G$ un graphe biparti de profil asym\'etrique $\Lambda$, dont les sommets gauches sont de degr\'e au plus $D$ et les sommet droits de degr\'e exactement $d$. Alors pour tout $T$, le sous-espace $X(G,L)$ des vecteurs de $\R^{V_R}$ dont la restriction aux voisins d'un sommet droit appartient toujours \`a $L$ est $(T,\frac{t}{T}\Lambda(T),\frac{\epsilon}{\sqrt{2D}})$-\'etal\'e.
\end{lemme}

On applique ce lemme d'abord à des graphes somme-produits, avec un $L$ initial construit à l'aide de matrices d'Hadamard. Par récurrence, on obtient des espaces vectoriels $X$ de dimension de plus en plus petite. A un moment donné, les graphes d'incidence prennent le relai.


\begin{thebibliography}{}

\bibitem[AC]{AC} Alon, N.; Chung, F. R. K. 
{\em Explicit construction of linear sized tolerant networks.} 
Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986).  Discrete Math.  \textbf{72}  (1988),  no. 1-3, 15--19.

\bibitem[BKT]{BKT} Bourgain, Jean; Katz, Netz; Tao, Terry.
\emph{A sum-product estimate in finite fields, and applications.}
Geom. Funct. Anal. \textbf{14} (2004), no. 1, 27--57. 

\bibitem[BKSSW]{BKSSW} Barak, Boaz; Kindler, Guy; Shaltiel, Ronen, Sudakov, Benny; Widgerson, Avi.
\emph{Simulating independance: new constructions of condensers, Ramsey graphs, dispersers, and extractors.}
STOC 2005 et 
http://www.math.ias.edu/$\sim$avi/PUBLICATIONS/MYPAPERS/bkssw04/bkssw04.pdf

\bibitem[BIW]{BIW} Barak, Boaz; Impagliazzo, Russel; Widgerson, Avi
\emph{Extracting randomness using few independant sources.}
SIAM J. Comput. \textbf{36} (2006), 1095-1118.
Aussi : FOCS 2004 et
http://www.math.ias.edu/$\sim$avi/PUBLICATIONS/MYPAPERS/BIW04/BIW.pdf

\bibitem[FLM]{FLM} Figiel, T.; Lindenstrauss, J.; Milman, V. D. 
\emph{The dimension of almost spherical sections of convex bodies.}  
Acta Math.  \textbf{139}  (1977), no. 1-2, 53--94. 

\bibitem[GG]{GG} Garnaev, A. Yu.; Gluskin, E. D.
\emph{The widths of a Euclidean ball.}
Dokl. Akad. Nauk SSSR \textbf{277} (1984), no. 5, 1048--1052. 

\bibitem[GLR]{GLR} Guruswami, Venkatesan; Lee, James; Razborov, Alexander.
\emph{Almost Euclidean subspaces of $\ell_1^N$ via expander codes.}
SODA 2008 et 
http://www.cs.washington.edu/homes/jrl/papers/spread.pdf

\bibitem[K]{K} Ka\v sin, B. S. 
\emph{The widths of certain finite-dimensional sets and classes of smooth functions.}
Izv. Akad. Nauk SSSR Ser. Mat.  \textbf{41 } (1977), no. 2, 334--351.

\bibitem[KT]{KT} Kashin, B.S., Temlyakov, V.N.
\emph{A remark on compressed sensing.}
http://www.dsp.ece.rice.edu/cs/KT2007.pdf

\bibitem[LPS]{LPS} Lubotzky, A.; Phillips, R.; Sarnak, P. 
{\em Ramanujan graphs.}  
Combinatorica  \textbf{8}  (1988),  no. 3, 261--277.
\end{thebibliography}

\end{document}