text:
\section{Introduction}
\label{sec:introduction}

Imagine that we only observe a few samples of a signal. Is it possible
to reconstruct this signal exactly or at least accurately?  For
example, suppose we observe a few entries of a vector $x \in \mathbb{R}^n$,
which we can think of as a digital signal or image. Can we recover the
large fraction of entries---of pixels if you will---that we have not
seen?  In general, everybody would agree that this is
impossible. However, if the signal is known to be sparse in the
Fourier domain and, by extension, in an incoherent domain, then
accurate---and even exact---recovery is possible by $\ell_1$
minimization \cite{CRT06}, see also \cite{GilbertStraussII} for other
algorithms, \cite{DonohoL1L0,DonohoTanner} for other types of
measurements, and \cite{Vetterli} for different ideas.  This
revelation is at the root of the rapidly developing field of
compressed sensing, and is already changing the way engineers think
about data acquisition, hence this special issue and others, see
\cite{SPM} for example. Concretely, if a signal has a sparse frequency
spectrum and we only have information about a few time or space
samples, then one can invoke linear programming to interpolate the
signal exactly. One can of course exchange time (or space) and
frequency, and recover sparse signals from just a few of their Fourier
coefficients as well.

Imagine now that we only observe a few entries of a data matrix. Then
is it possible to accurately---or even exactly---guess the entries
that we have not seen?  For example, suppose we observe a few movie
ratings from a large data matrix in which rows are users and columns
are movies (we can only observe a few ratings because each user is
typically rating a few movies as opposed to the tens of thousands of
movies which are available). Can we predict the rating a user would
hypothetically assign to a movie he/she has not seen? In general,
everybody would agree that recovering a data matrix from a subset of
its entries is impossible. However, if the unknown matrix is known to
have low rank or approximately low rank, then accurate and even exact
recovery is possible by nuclear norm minimization
\cite{CR08,CT09}. This revelation, which to some extent is inspired by
the great body of work in compressed sensing, is the subject of this
paper.

From now on, we will refer to the problem of inferring the many
missing entries as the {\em matrix completion} problem. By extension,
inferring a matrix from just a few linear functionals will be called
the {\em the low-rank matrix recovery} problem. Now just as sparse
signal recovery is arguably of paramount importance these days, we do
believe that matrix completion and, in general, low-rank matrix
recovery is just as important, and will become increasingly studied in
years to come. For now, we give a few examples of applications in which
these problems do come up.

\begin{itemize}
\item {\em Collaborative filtering.}  In a few words, collaborative
  filtering is the task of making automatic predictions about the
  interests of a user by collecting taste information from many users
  \cite{Goldberg92}. Perhaps the most well-known implementation of
  collaborating filtering is the Netflix recommendation system alluded
  to earlier, which seeks to make rating predictions about unseen
  movies. This is a matrix completion problem in which the unknown
  full matrix has approximately low rank because only a few factors
  typically contribute to an individual's tastes or preferences. In
  the new economy, companies are interested predicting musical
  preferences (Apple Inc.), literary preferences (Amazon, Barnes and
  Noble) and many other such things.

\item {\em System identification.} In control, one would like to fit a
  discrete-time linear time-invariant state-space model
\begin{align*}
x(t + 1) & = Ax(t) + Bu(t),\\
y(t) & =  C x(t) + Du(t)
\end{align*}
to a sequence of inputs $u(t) \in \mathbb{R}^m$ and outputs $y(t) \in R^p$, $t
= 0, \ldots, N$. The vector $x(t) \in \mathbb{R}^n$ is the state of the system
at time $t$, and $n$ is the order of the system model.  From the
input/output pair $\{(u(t), y(t)) : t = 0, \ldots N\}$, one would like
to recover the dimension of the state vector $n$ (the model order),
and the dynamics of the system, i.e.~the matrices $A$, $B$, $C$, $D$,
and the initial state $x(0)$. This problem can be cast as a low-rank
matrix recovery problem, see \cite{VandenbergheNuc} and references
therein.

\item {\em Global positioning.} Finding the global positioning of
  points in Euclidean space from a local or partial set of pairwise
  distances is a problem in geometry that emerges naturally in sensor
  networks \cite{TohYe,Singer1,Singer2}. For example, because of power
  constraints, sensors may only be able to construct reliable distance
  estimates from their immediate neighbors. From these estimates, we
  can form a partially observed distance matrix, and the problem is to
  infer all the pairwise distances from just a few observed ones so
  that locations of the sensors can be reliably estimated.  This
  reduces to a matrix completion problem where the unknown matrix is
  of rank two if the sensors are located in the plane, and three if
  they are located are in space.

\item {\em Remote sensing.} The MUSIC algorithm \cite{MUSIC} is
  frequently used to determine the direction of arrival of incident
  signals in a coherent radio-frequency environment. In a typical
  application, incoming signals are being recorded at various sensor
  locations, and this algorithm operates by extracting the directions
  of wave arrivals from the covariance matrix obtained by computing
  the correlations of the signals received at all sensor pairs. In
  remote sensing applications, one may not be able to estimate or
  transmit all correlations because of power constraints
  \cite{Brian}. In this case, we would like to infer a full covariance
  matrix from just a few observed partial correlations. This is a
  matrix completion problem in which the unknown signal covariance
  matrix has low rank since it is equal to the number of incident
  waves, which is usually much smaller than the number of sensors.
\end{itemize}

There are of course many other examples including the
structure-from-motion problem \cite{Tomasi,ChenSuter} in computer
vision, multi-class learning in data analysis \cite{Argyriou07,
  Amit07}, and so on.

This paper investigates whether or not one can recover low rank
matrices from fewer entries, and if so, how and how well. In Section
\ref{sec:exact}, we will study the noiseless problem in which the
observed entries are precisely those of the unknown matrix. Section
\ref{sec:stable} examines the more common situation in which the few
available entries are corrupted with noise. We complement our study
with a few numerical experiments demonstrating the empirical
performance of our methods in Section \ref{sec:numerical} and conclude
with a short discussion (Section \ref{sec:discussion}).

Before we begin, it is best to provide a brief summary of the
notations used throughout the paper. We shall use three norms of a
matrix $X \in \mathbb{R}^{n_1 \times n_2}$ with singular values
$\{\sigma_k\}$. The \emph{spectral norm} is denoted by $\|\mtx{X}\|$
and is the largest singular value. The Euclidean inner product between
two matrices is defined by the formula $\<\mtx{X}, \mtx{Y}\> :=
\operatorname{trace}(\mtx{X}^* \mtx{Y})$, and the corresponding Euclidean norm is
called the \emph{Frobenius norm} and denoted by $\|X\|_F$ (note that
this is the $\ell_2$ norm of the vector of singular values). The
\emph{nuclear norm} is denoted by $\|\mtx{X}\|_* := \sum_k \sigma_k$
and is the sum of singular values (the $\ell_1$ norm of the vector
$\{\sigma_k\}$). As is standard, $X \succeq Y$ means that $X - Y$ is
positive semidefinite.

Further, we will also manipulate linear transformation which acts on
the space $\mathbb{R}^{n_1 \times n_2}$, and we will use calligraphic letters
for these operators as in ${\mathcal A}(\mtx{X})$. In particular, the
identity operator on this space will be denoted by $\mathcal{I}: \mathbb{R}^{n_1
  \times n_2} \to \mathbb{R}^{n_1 \times n_2}$. We use the same convention as
above, and $\mathcal{A} \succeq \mathcal{I}$ means that $\mathcal{A} -
\mathcal{I}$ (seen as a big matrix) is positive semidefinite.

We use the usual asymptotic notation, for instance writing $O(M)$ to
denote a quantity bounded in magnitude by $C M$ for some absolute
constant $C > 0$.

\section{Exact Matrix Completion}
\label{sec:exact}

From now on, $M \in \mathbb{R}^{n_1 \times n_2}$ is a matrix we would like to
know as precisely as possible. However, the only information available
about M is a sampled set of entries $M_{ij}$, $(i,j) \in \Omega$,
where $\Omega$ is a subset of the complete set of entries $[n_1]
\times [n_2]$. (Here and in the sequel, $[n]$ denotes the list
$\{1,\ldots,n\}$.) It will be convenient to summarize the information
available via $\mathcal{P}_\Omega(M)$, where the sampling operator $\mathcal{P}_\Omega: \mathbb{R}^{n_1
  \times n_2} \to \mathbb{R}^{n_1 \times n_2}$ is defined by
\[
[\mathcal{P}_\Omega(X)]_{ij} = \begin{cases} X_{ij}, & (i,j) \in \Omega,\\
  0, & \text{otherwise}. \end{cases}
\]
Thus, the question is whether it is possible to recover our matrix
only from the information $\mathcal{P}_\Omega(\mtx{M})$.  We will assume that the
entries are selected at random without replacement as to avoid trivial
situations in which a row or a column is unsampled, since matrix
completion is clearly impossible in such cases. (If we have no data
about a specific user, how can we guess his/her preferences? If we
have no distance estimates about a specific sensor, how can we guess
its distances to all the sensors?)

Even with the information that the unknown matrix $M$ has low rank, this
problem may be severely ill posed. Here is an example that shows why:
let $x$ be a vector in $\mathbb{R}^n$ and consider the $n \times n$ rank-1
matrix
\[
\mtx{M} = \vct{e}_1 \vct{x}^* = \begin{bmatrix}
 x_1 & x_2 & x_3 & \cdots & x_{n-1} & x_n \\
 0 & 0 & 0 & \cdots & 0 & 0 \\
 0 & 0 & 0 & \cdots & 0 & 0 \\
 \vdots & \vdots & \vdots &  \vdots & \vdots & \vdots \\
 0 & 0 & 0 & \cdots & 0 & 0
\end{bmatrix},
\]
where $e_1$ is the first vector in the canonical basis of $\mathbb{R}^n$.
Clearly, this matrix cannot be recovered from a subset of its
entries. Even if one sees 95\% of the entries sampled at random, then
we will miss elements in the first row with very high probability,
which makes the recovery of the vector $x$, and by extension of $M$,
impossible. The analogy in compressed sensing is that one obviously
cannot recover a signal assumed to be sparse in the time domain, by
subsampling in the time domain!

This example shows that one cannot hope to complete the matrix if some
of the singular vectors of the matrix are extremely sparse---above,
one cannot recover $M$ without sampling all the entries in the first
row, see \cite{CR08} for other related pathological examples. More
generally, if a row (or column) has no relationship to the other rows
(or columns) in the sense that it is approximately orthogonal, then
one would basically need to see all the entries in that row to recover
the matrix $M$.
Such informal considerations led the authors of \cite{CR08} to
introduce a geometric incoherence assumption,
but for the moment, we will discuss an even simpler notion which
forces the singular vectors of $M$ to be spread across all
coordinates. To express this condition, recall the singular value
decomposition (SVD) of a matrix of rank $r$,
\begin{equation}
  \label{eq:svd}
  \mtx{M} = \sum_{k \in [r]} \sigma_k \vct{u}_k \vct{v}_k^*,
\end{equation}
in which $\sigma_1,\ldots,\sigma_r \geq 0$ are the singular values,
and $u_1,\ldots,u_r \in \mathbb{R}^{n_1}$, $v_1, \ldots, v_r \in \mathbb{R}^{n_2}$ are
the singular vectors. Our assumption is as follows:
\begin{equation}
  \label{eq:bdd}
  \|u_k\|_{\ell_\infty} \le \sqrt{\mu_B/n_1}, \quad   \|v_k\|_{\ell_\infty} \le \sqrt{\mu_B/n},
\end{equation}
for some $\mu_B \ge 1$, where the $\ell_\infty$ norm is of course
defined by $\|x\|_{\ell_\infty} = \max_i |x_i|$. We think of $\mu_B$
as being small, e.g. $O(1)$, so that the singular vectors are not too
spiky as explained above.

If the singular vectors of $M$ are sufficiently spread, the hope is
that there is a unique low-rank matrix which is consistent with the
observed entries. If this is the case, one could, in principle,
recover the unknown matrix by solving
\begin{equation}
\label{eq:rank}
  \begin{array}{ll}
    \text{minimize}   & \quad \operatorname{rank}(X)\\
    \text{subject to} & \quad \mathcal{P}_\Omega(\mtx{X}) = \mathcal{P}_\Omega(\mtx{M}),
 \end{array}
\end{equation}
where $X \in \mathbb{R}^{n_1 \times n_2}$ is the decision variable.
Unfortunately, not only is this algorithm NP-hard, but all known
algorithms for exactly solving it are doubly exponential in theory and
in practice \cite{Grigoriev84}. This is analogous to the
intractability of $\ell_0$-minimization in sparse signal recovery.

A popular alternative is the convex relaxation
\cite{FazelThesis,fazelrank,Recht07,CR08,CT09}
\begin{equation}
\label{eq:cvx2}
  \begin{array}{ll}
    \text{minimize}   & \quad \|\mtx{X}\|_*\\
    \text{subject to} & \quad \mathcal{P}_\Omega(\mtx{X}) = \mathcal{P}_\Omega(\mtx{M}),
 \end{array}
\end{equation}
(see \cite{Beck98,Mesbahi97} for the earlier related trace heuristic).
Just as $\ell_1$-minimization is the tightest convex relaxation of the
combinatorial $\ell_0$-minimization problem in the sense that the
$\ell_1$ ball of $\mathbb{R}^n$ is the convex hull of unit-normed 1-sparse
vectors (i.e.~vectors with at most one nonzero entry), nuclear-norm
minimization is the tightest convex relaxation of the NP-hard rank
minimization problem. To be sure, the nuclear ball $\{\mtx{X} \in
\mathbb{R}^{n_1 \times n_2} : \|\mtx{X}\|_* \le 1\}$ is the convex hull of the
set of rank-one matrices with spectral norm bounded by one. Moreover,
in compressed sensing, $\ell_1$ minimization subject to linear
equality constraints can be cast as a linear program (LP) for the
$\ell_1$ norm has an LP characterization: indeed for each $x \in
\mathbb{R}^n$, $\|x\|_{\ell_1}$ is the optimal value of
\begin{equation*}
  \begin{array}{ll}
    \text{maximize}   & \quad \<u,x\>\\
    \text{subject to} & \quad \|u\|_{\ell_\infty} \le 1,
 \end{array}
\end{equation*}
with decision variable $u \in \mathbb{R}^n$. In the same vein, the nuclear
norm of $X \in \mathbb{R}^{n_1 \times n_2}$ has the SDP characterization
\begin{equation}
\label{eq:SDP}
 \begin{array}{ll}
   \text{maximize}   & \quad \<W,X\> \\
   \text{subject to} & \quad \|W\| \le 1,
 \end{array}
\end{equation}
with decision variable $W \in \mathbb{R}^{n_1 \times n_2}$. This expresses the
fact that the spectral norm is dual to the nuclear norm. The
constraint on the spectral norm of $W$ is an SDP constraint since it
is equivalent to
\[
\begin{bmatrix} I_{n_1} & \mtx{W}\\
  \mtx{W}^* & \mtx{I}_{n_2}
\end{bmatrix} \succeq 0,
\]
where $I_{n}$ is the $n \times n$ identity matrix.  Hence,
\eqref{eq:cvx2} is an SDP, which one can express by writing $\|X\|_*$
as the optimal value of the SDP dual to \eqref{eq:SDP}.

In \cite{CT09}, it is proven that nuclear-norm minimization succeeds
nearly as soon as recovery is possible by any method whatsoever.
\begin{theorem}\cite{CT09}
\label{teo:main1}
Let $M \in \mathbb{R}^{n_1 \times n_2}$ be a fixed matrix of rank $r = O(1)$
obeying \eqref{eq:bdd} and set $n := \max(n_1,n_2)$.  Suppose we
observe $m$ entries of $\mtx{M}$ with locations sampled uniformly at
random.  Then there is a positive numerical constant $C$ such that if
  \begin{equation}
    \label{eq:main1}
    m \ge C\, \mu_B^4\, n  \log^2 n,
  \end{equation}
  then $M$ is the unique solution to \eqref{eq:cvx2} with probability
  at least $1 - n^{-3}$.  In other words: with high probability,
  nuclear-norm minimization recovers all the entries of $\mtx{M}$ with
  no error.
\end{theorem}

As a side remark, one can obtain a probability of success at least
$1-n^{-\beta}$ for $\beta$ by taking $C$ in \eqref{eq:main1} of the
form $C' \beta$ for some universal constant $C'$.

An $n_1 \times n_2$ matrix of rank $r$ depends upon $r(n_1 + n_2 - r)$
degrees of freedom\footnote{This can be seen by counting the degrees
  of freedom in the singular value decomposition.}. When $r$ is small,
the number of degrees of freedom is much less than $n_1 n_2$ and this
is the reason why subsampling is possible. (In compressed sensing, the
number of degrees of freedom corresponds to the sparsity of the
signal; i.e.~the number of nonzero entries.) What is remarkable here,
is that exact recovery by nuclear norm minimization occurs as soon as
the sample size exceeds the number of degrees of freedom by a couple
of logarithmic factors.  Further, observe that if $\Omega$ completely
misses one of the rows (e.g.~one has no rating about one user) or one
of the columns (e.g.~one has no rating about one movie), then one
cannot hope to recover even a matrix of rank $1$ of the form $M = x
y^*$.  Thus one needs to sample every row (and also every column) of
the matrix.  When $\Omega$ is sampled at random, it is well
established that one needs at least on the order $O(n \log n)$ for
this to happen as this is the famous coupon collector's
problem. Hence, \eqref{eq:main1} misses the information theoretic
limit by at most a logarithmic factor.

To obtain similar results for all values of the rank, \cite{CT09}
introduces the {\em strong incoherence property} with parameter
$\mu$ stated below.
\begin{description}
\item[{A1}] Let $P_U$ (resp.~$P_V$) be the orthogonal projection onto
  the singular vectors $u_1, \ldots, u_r$ (resp.~$v_1, \ldots$, $v_r$).
  For all pairs $(a,a') \in [n_1] \times [n_1]$ and $(b,b') \in [n_2]
  \times [n_2]$,
\begin{align*}
\Bigl|\<e_a, P_U e_{a'}\> - \frac{r}{n_1} 1_{a = a'}\Bigr| & \le \mu \frac{\sqrt{r}}{n_1},\\
\Bigl|\<e_b, P_V e_{b'}\> - \frac{r}{n_2} 1_{b = b'}\Bigr| & \le
\mu \frac{\sqrt{r}}{n_2}.
\end{align*}
\item[{A2}] Let $E$ be the ``sign matrix'' defined by
  \begin{equation}
    \label{eq:E}
    E = \sum_{k \in [r]} u_k v_k^*.
  \end{equation}
  For all $(a,b) \in [n_1] \times [n_2]$,
\begin{equation*}\label{eab}
 |E_{ab}| \le \mu \frac{\sqrt{r}}{\sqrt{n_1 n_2}}.
\end{equation*}
\end{description}

These conditions do not assume anything about the singular values. As
we will see, incoherent matrices with a small value of the strong
incoherence parameter $\mu$ can be recovered from a minimal set of
entries. Before we state this result, it is important to note that
many model matrices obey the strong incoherence property with a small
value of $\mu$.
\begin{itemize}
\item Suppose the singular vectors obey \eqref{eq:bdd} with $\mu_B =
  O(1)$ (which informally says that the singular vectors are not
  spiky), then with the exception of a very few peculiar matrices, $M$
  obeys the strong incoherence property with $\mu = O(\sqrt{\log n})$.

\item Assume that the column matrices $[u_1, \ldots, u_r]$ and $[v_1,
  \ldots, v_r]$ are independent random orthogonal matrices, then with
  high probability, $M$ obeys the strong incoherence property with
  $\mu = O(\sqrt{\log n})$, at least when $r \ge \log n$ as to avoid
  small samples effects.
\end{itemize}

The sampling result below is general, nonasymptotic and optimal up to
a few logarithmic factors.
\begin{theorem}
  \label{teo:main2} \cite{CT09} With the same notations as in Theorem
  \ref{teo:main1}, there is a numerical constant $C$ such that if
  \begin{equation}
    \label{eq:main2}
    m \ge C\, \mu^2\, nr \log^6 n,
  \end{equation}
  $M$ is the unique solution to \eqref{eq:cvx2} with probability at
  least $1 - n^{-3}$.
\end{theorem}

In other words, if a matrix is strongly incoherent and the cardinality
of the sampled set is about the number of degrees of freedom times a
few logarithmic factors, then nuclear-norm minimization is exact. This
improves on an earlier result of Cand\`es and Recht \cite{CR08} who
proved---under slightly different assumptions---that on the order of
$n^{6/5} r \log n$ samples were sufficient, at least for values of the
rank obeying $r \le n^{1/5}$.

We would like to point out a result of a broadly similar nature, but
with a completely different recovery algorithm and with a somewhat
different range of applicability, which was recently established by
Keshavan, Oh, and Montanari \cite{MontanariISIT}. Their conditions are
related to the incoherence property introduced in \cite{CR08}, and are
also satisfied by a number of reasonable random matrix models. There
is, however, another condition which states that the singular values
of the unknown matrix cannot be too large or too small (the ratio
between the top and lowest value must be bounded).  This algorithm 1)
trims each row and column with too few entries; i.e~replaces the
entries in those rows and columns by zero and 2) computes the SVD of
the trimmed matrix and truncate it as to only keep the top $r$
singular values (note that the value of $r$ is needed here). The
result is that under some suitable conditions discussed above, this
recovers a good approximation to the matrix $M$ provided that the
number of samples be on the order of $nr$. The recovery is not exact
but only approximate although the authors have announced that one
could add extra steps to the algorithm to provide an exact recovery if
one has more samples (on the order of $nr \log n$). At the time of
this writing, such results are not yet publicly available.

\subsection{Geometry and dual certificates}
\label{sec:T}

We cannot possibly rehash the proof of Theorem \ref{teo:main2} from
\cite{CT09} in this paper, or even explain the main technical steps,
because of space limitations. We will, however, detail sufficient and
almost necessary conditions for the low-rank matrix $M$ to be the
unique solution to the SDP \eqref{eq:cvx2}. This will be useful to
establish stability results.

\begin{figure}
 \centering
\includegraphics[scale=.4]{svt.pdf}
\caption{\small The blue shape (courtesy of B.~Recht) represents the
  nuclear ball (see the main text), and the plane the feasible set
  (courtesy .}
\label{fig:nuclear_ball}
\end{figure}
The recovery is exact if the feasible set is tangent to the nuclear
ball at the point $M$, see Figure \ref{fig:nuclear_ball} which
represents the set of points $(x,y,z) \in \mathbb{R}^3$ such that the $2
\times 2$ {\em symmetric} matrix $\begin{bmatrix} x & y \\ y &
  z \end{bmatrix}$ has nuclear norm bounded by one.  To express this
mathematically\footnote{In general, $M$ minimizes the nuclear norm
  subject to the linear constraints $\mathcal{A}(X) = b$, $\mathcal{A}
  : \mathbb{R}^{n_1 \times n_2} \rightarrow \mathbb{R}^{m}$, if and only if there is
  $\lambda \in \mathbb{R}^m$ such that $\mathcal{A}^*(\lambda) \in \partial
  \|M\|_*$.}, standard duality theory asserts that $M$ is a solution
to \eqref{eq:cvx2} if and only if there exists a dual matrix $\Lambda$
such that $\mathcal{P}_\Omega(\Lambda)$ is a subgradient of the nuclear norm at $M$,
written as
\begin{equation}
  \label{eq:dual}
  \mathcal{P}_\Omega(\Lambda) \in \partial \|M\|_*.
\end{equation}
Recall the SVD \eqref{eq:svd} of $M$ and the ``sign matrix'' $E$
\eqref{eq:E}. It is is well-known that $Z \in \partial \|M\|_*$ if and
only if $Z$ is of the form,
\begin{equation}
  \label{eq:sub1}
  Z = E + W,
\end{equation}
where
\begin{equation}
\label{eq:sub2}
P_U W = 0, \quad W P_V = 0, \quad \|W\| \le 1.
\end{equation}
In English, $Z$ is a subgradient if it can be decomposed as the sign
matrix plus another matrix with spectral norm bounded by one, whose
column (resp.~row) space is orthogonal to the span of $u_1, \ldots,
u_r$, (resp.~of $v_1, \ldots, v_r$). Another way to put this is by
using notations introduced in \cite{CR08}. Let $T$ be the linear space
spanned by elements of the form ${u}_k {x}^*$ and ${y} {v}_k^*$, $k
\in [r]$, and let $T^\perp$ be the orthogonal complement to $T$. Note
that $T^\perp$ is the set of matrices obeying $P_U W = 0$ and $W P_V =
0$. Then, $Z \in \partial \|M\|_*$ if and only if
\[
Z = E + \mathcal{P}_{T^\perp}(Z), \quad \|\mathcal{P}_{T^\perp}(Z)\| \le 1.
\]
This motivates the following definition.
\begin{definition}[Dual certificate] We say that $\Lambda$ is a dual
  certificate if $\Lambda$ is supported on $\Omega$ ($\Lambda =
  \mathcal{P}_\Omega(\Lambda)$), $\mathcal{P}_T(\Lambda) = E$ and $\|\mathcal{P}_{T^\perp}(\Lambda)\| \le 1$.
\end{definition}

Before continuing, we would like to pause to observe the relationship
with $\ell_1$ minimization. The point $x^\star \in \mathbb{R}^n$ is solution
to
\begin{equation}
\label{eq:l1}
  \begin{array}{ll}
    \text{minimize}   & \quad \|x\|_{\ell_1}\\
    \text{subject to} & \quad Ax = b,
 \end{array}
\end{equation}
with $A \in \mathbb{R}^{m \times n}$ if and only if there exists $\lambda \in
\mathbb{R}^m$ such that $ A^* \lambda \in \partial \|x^\star\|_{\ell_1}$.
Note that if $S^\star$ is the support of $x^\star$, $z \in \partial
\|x^\star\|_{\ell_1}$ is equivalent to
\[
z = e + w, \quad e = \begin{cases} \textrm{sgn}(x^\star_i), & i \in S^\star,\\
  0, & i \notin  S^*, \end{cases}
\]
and
\[
w_i = 0 \text{ for all }  i \in S, \quad \|w\|_{\ell_\infty} \le 1.
\]
Hence, there is a clear analogy and one can think of $T$ defined above
as playing the role of the support set in the sparse recovery problem.

With this in place, we shall make use of the following lemma from \cite{CR08}:
\begin{lemma}
  \label{teo:useful} \cite{CR08} Suppose there exists a dual
  certificate $\Lambda$ and consider any $H$ obeying $\mathcal{P}_\Omega(H) =
  0$. Then
\[
\|M + H\|_* \ge \|M\|_* - (1-\|\mathcal{P}_{T^\perp}(\Lambda)\|) \|\mathcal{P}_{T^\perp}(H)\|_*.
\]
\end{lemma}

\begin{proof}
For any $Z \in \partial \|M\|_*$, we have
\[
\|M+H\|_* \ge \|M\|_* + \<Z, H\>.
\]
With $\Lambda = E + \mathcal{P}_{T^\perp}(\Lambda)$ and $Z = E + \mathcal{P}_{T^\perp}(Z)$, we have
\begin{align*}
\|M+H\|_* & \ge \|M\|_* + \<\Lambda,H\> + \<\mathcal{P}_{T^\perp}(Z-\Lambda),H\>\\
& = \|M\|_* + \<Z-\Lambda,\mathcal{P}_{T^\perp}(H)\>
\end{align*}
since $\mathcal{P}_\Omega(H) = 0$. Now we use the fact that the nuclear and spectral
norms are dual to one another. In particular, there exists $\|Z\| \le
1$ such that $\<Z,\mathcal{P}_{T^\perp}(H)\> = \|\mathcal{P}_{T^\perp}(H)\|_*$ and $|\<\Lambda,
\mathcal{P}_{T^\perp}(H)\>| = |\<\mathcal{P}_{T^\perp}(\Lambda),\mathcal{P}_{T^\perp}(H)\>| \le \|\mathcal{P}_{T^\perp}(\Lambda)\|
\|\mathcal{P}_{T^\perp}(H)\|_*$. Therefore,
\[
\|M+H\|_* \ge  \|M\|_* + (1-\|\mathcal{P}_{T^\perp}(\Lambda)\|) \|\mathcal{P}_{T^\perp}(H)\|_*,
\]
which concludes the proof.
\end{proof}
A consequence of this lemma are the sufficient conditions below.
\begin{lemma}
\label{teo:dual}
\cite{CR08} Suppose there exists a dual certificate obeying
$\|{\mathcal P}_{T^\perp}(\mtx{Y})\| < 1$ and that the restriction
$\mathcal{P}_\Omega\downharpoonright_T: T \to \mathcal{P}_\Omega(\mathbb{R}^{n \times n})$ of the (sampling)
operator $\mathcal{P}_\Omega$ restricted to $T$ is injective.  Then $\mtx{M}$ is the
unique solution to the convex program \eqref{eq:cvx2}.
\end{lemma}

\begin{proof}
  Consider any feasible perturbation $M + H$ obeying $\mathcal{P}_\Omega(H) =
  0$. Then by assumption, Lemma \ref{teo:useful} gives
\[
\|M+H\|_* > \|M\|_*
\]
unless $\mathcal{P}_{T^\perp}(H) = 0$. Assume then that $\mathcal{P}_{T^\perp}(\mtx{H}) = 0$; that is to
say, $\mtx{H} \in T$. Then $\mathcal{P}_\Omega(\mtx{H}) = 0$ implies that $\mtx{H} =
0$ by the injectivity assumption. The conclusion is that $M$ is the
unique minimizer since any nontrivial perturbation increases the
nuclear norm.
\end{proof}

The methods for proving that matrix completion by nuclear minimization
is exact, consist in constructing a dual certificate.
\begin{theorem}
  \label{teo:certificate}
  \cite{CT09} Under the assumptions of either Theorem \ref{teo:main1}
  or Theorem \ref{teo:main2}, there exists a dual certificate obeying
  $\|\mathcal{P}_{T^\perp}(\Lambda)\| \le 1/2$. In addition, if $p = m/(n_1 n_2)$ is
  the fraction of observed entries, the operator $\mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T : T
  \rightarrow T$ is one-to-one and obeys
  \begin{equation}
    \label{eq:rudelson}
    \frac{p}{2} \, \mathcal{I}  \preceq \mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T  \preceq  \frac{3p}{2} \, \mathcal{I},
  \end{equation}
  where $\mathcal{I} : T \rightarrow T$ is the identity operator.
\end{theorem}

The second part, namely, \eqref{eq:rudelson} shows that the mapping
$\mathcal{P}_\Omega : T \rightarrow \mathbb{R}^{n_1 \times n_2}$ is injective. Hence, the
sufficient conditions of Lemma \ref{teo:dual} are verified, and the
recovery is exact. What is interesting, is that the existence of a
dual certificate together with the near-isometry
\eqref{eq:rudelson}---in fact, the lower bound---are sufficient to
establish the robustness of matrix completion vis a vis noise.

\section{Stable Matrix Completion}
\label{sec:stable}

In any real world application, one will only observe a few entries
corrupted at least by a small amount of noise. In the Netflix problem,
users' ratings are uncertain. In the system identification problem,
one cannot determine the locations $y(t)$ with infinite precision. In
the global positioning problem, local distances are imperfect. And
finally, in the remote sensing problem, the signal covariance matrix
is always modeled as being corrupted by the covariance of noise
signals. Hence, to be broadly applicable, we need to develop results
which guarantee that reasonably accurate matrix completion is possible
from noisy sampled entries. This section develops novel results
showing that this is, indeed, the case.

Our noisy model assumes that we observe
\begin{equation}
  \label{eq:noisy}
  Y_{ij} = M_{ij} + Z_{ij}, \quad (i,j) \in \Omega,
\end{equation}
where $\{Z_{ij} : (i,j) \in \Omega\}$ is a noise term which may be
stochastic or deterministic (adversarial). Another way to express this
model is as
\[
\mathcal{P}_\Omega(Y) = \mathcal{P}_\Omega(M) + \mathcal{P}_\Omega(Z),
\]
where $Z$ is an $n \times n$ matrix with entries $Z_{ij}$ for $(i,j)
\in \Omega$ (note that the values of $Z$ outside of $\Omega$ are
irrelevant). All we assume is that $\|\mathcal{P}_\Omega(Z)\|_F \le \delta$ for some
$\delta > 0$. For example, if $\{Z_{ij}\}$ is a white noise sequence
with standard deviation $\sigma$, then $\delta^2 \le (m + \sqrt{8m})
\sigma^2$ with high probability, say.  To recover the unknown matrix,
we propose solving the following optimization problem:
\begin{equation}
  \label{eq:lasso}
  \begin{array}{ll}
    \textrm{minimize}   & \quad \|X\|_*\\
    \textrm{subject to} & \quad \|\mathcal{P}_\Omega(X - Y)\|_F \le \delta
 \end{array}
\end{equation}
Among all matrices consistent with the data, find the one with minimum
nuclear norm. This is also an SDP, and let $\hat M$ be the solution to
this problem.

Our main result is that this reconstruction is accurate.
\begin{theorem}
\label{teo:stable}
With the notations of Theorem \ref{teo:certificate}, suppose there
exists a dual certificate obeying $\|\mathcal{P}_{T^\perp}(\Lambda)\| \le 1/2$ and that
$\mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T \succeq \frac{p}{2} \mathcal{I}$ (both these conditions are
true with very large probability under the assumptions of the
noiseless recovery Theorems \ref{teo:main1} and \ref{teo:main2}). Then
$\hat M$ obeys
  \begin{equation}
    \label{eq:stable}
    \|M - \hat M\|_F \le  4 \sqrt{\frac{C_p \min(n_1,n_2)}{p}} \, \delta + 2  \delta,
  \end{equation}
  with $C_p = 2 + p$.
\end{theorem}

For small values of $p$ (recall this is the fraction of observed
entries), the error is of course at most just about $
4\sqrt{\frac{2\min(n_1,n_2)}{p}}\, \delta$.  As we will see from the
proof, there is nothing special about 1/2 in the condition
$\|\mathcal{P}_{T^\perp}(\Lambda)\| \le 1/2$. All we need is that there is a dual
certificate obeying $\|\mathcal{P}_{T^\perp}(\Lambda)\| \le a$ for some $a < 1$ (the
value of $a$ only influences the numerical constant in
\eqref{eq:stable}). Further, when $Z$ is random, \eqref{eq:stable}
holds on the event $\|\mathcal{P}_\Omega(Z)\|_F \le \delta$.

Roughly speaking, our theorem states the following: {\em when perfect
  noiseless recovery occurs, then matrix completion is stable vis a
  vis perturbations}.  To be sure, the error is proportional to the
noise level $\delta$; when the noise level is small, the error is
small. Moreover, improving conditions under which noiseless recovery
occurs, has automatic consequences for the more realistic recovery
from noisy samples.

A significant novelty here is that there is just no equivalent of this
result in the compressed sensing or statistical literature for our
matrix completion problem does not obey the {\em restricted isometry
  property} (RIP) \cite{CT05}. For matrices, the RIP would
assume that the sampling operator obeys
\begin{equation}
\label{eq:rip}
(1-\delta) \|X\|_F^2 \le \frac{1}{p} \|\mathcal{P}_\Omega(X)\|_F^2 \le (1+\delta)
\|X\|_F^2
\end{equation}
for all matrices $X$ with sufficiently small rank and $\delta < 1$
sufficiently small \cite{Recht07}. However, the RIP does not hold
here. To see why, let the sampled set $\Omega$ be arbitrarily chosen
and fix $(i,j) \notin \Omega$. Then the rank-1 matrix $e_i e_j^*$
whose $(i,j)$th entry is 1, and vanishes everywhere else, obeys
$\mathcal{P}_\Omega(e_i e_j^*) = 0$. Clearly, this violates \eqref{eq:rip}.

It is nevertheless instructive to compare \eqref{eq:stable} with the
bound one would achieve if the RIP \eqref{eq:rip} were true. In this
case, \cite{FCRP08} would give
\[
\|\hat M - M\|_F \le C_0 p^{-1/2}\, \delta
\]
for some numerical constant $C_0$. That is, an estimate which would be
better by a factor proportional to $1/\sqrt{\min(n_1,n_2)}$.  It would be
interesting to know whether or not estimates, which are as good as
what is achievable under the RIP, hold for the RIPless matrix
completion problem.  We will return to such comparisons later (Section
\ref{sec:oracle}).

We close this section by emphasizing that our methods are also applicable
to sparse signal recovery problems in which the RIP does not hold.

\subsection{Proof  of  Theorem \ref{teo:stable}}
\label{sec:proof}

\newcommand{H_\Omega}{H_\Omega}
\newcommand{H_{\Omega^c}}{H_{\Omega^c}}

We use the notation of the previous section, and begin the proof by
observing two elementary properties. The first is that since $M$ is
feasible for \eqref{eq:lasso}, we have the {\em cone constraint}
\begin{equation}
  \label{eq:cone}
   \|\hat M\|_* \le \|M\|_*.
\end{equation}
The second is that the triangle inequality implies the {\em tube
  constraint}
\begin{align}
  \nonumber
  \|\mathcal{P}_\Omega(\hat M - M)\|_F & \le \|\mathcal{P}_\Omega(\hat M - Y)\|_F + \|\mathcal{P}_\Omega(Y - M)\|_F  \\
  \label{eq:tube}
& \le 2\delta,
\end{align}
since $M$ is feasible. We will see that under our hypotheses,
\eqref{eq:cone} and \eqref{eq:tube} imply that $\hat M$ is close to
$M$.  Set $\hat M = M + H$ and put $H_\Omega := \mathcal{P}_\Omega(H)$, $H_{\Omega^c} := \mathcal{P}_{\Omega^c}(H)$
for short. We need to bound $\|H\|^2_F = \|H_\Omega\|_F^2 + \|H_{\Omega^c}\|_F^2$,
and since \eqref{eq:tube} gives $\|H_\Omega\|_F \le 2\delta$, it suffices to
bound $\|H_{\Omega^c}\|_F$. Note that by the Pythagorean identity, we have
\begin{equation}
\label{eq:pythagoras}
\|H_{\Omega^c}\|_F^2 = \|\mathcal{P}_T(H_{\Omega^c})\|_F^2 + \|\mathcal{P}_{T^\perp}(H_{\Omega^c})\|_F^2,
\end{equation}
and it is thus sufficient to bound each term in the right hand-side.

We start with the second term. Let $\Lambda$ be a dual certificate obeying
$\|\mathcal{P}_{T^\perp} (\Lambda)\| \le 1/2$, we have
\[
 \|M+H\|_* \ge \|M+H_{\Omega^c}\|_* - \|H_\Omega\|_*
\]
and
\[
\|M+H_{\Omega^c}\|_* \ge  \|M\|_* + [1-\|\mathcal{P}_{T^\perp} (\Lambda)\|] \|\mathcal{P}_{T^\perp} (H_{\Omega^c})\|_*.
\]
The second inequality follows from Lemma \ref{teo:useful}. Therefore,
with $\|\mathcal{P}_{T^\perp} (\Lambda)\| \le 1/2$, the cone constraint gives
\[
\|M\|_* \ge \|M\|_* + \frac{1}{2} \|\mathcal{P}_{T^\perp} (H_{\Omega^c})\|_* - \|H_\Omega\|_*,
\]
or, equivalently,
\[
 \|\mathcal{P}_{T^\perp} (H_{\Omega^c})\|_* \le  2 \|H_\Omega\|_*.
\]
Since the nuclear norm dominates the Frobenius norm, $\|\mathcal{P}_{T^\perp}
(H_{\Omega^c})\|_F \le \|\mathcal{P}_{T^\perp} (H_{\Omega^c})\|_*$, we have
\begin{align}
\nonumber
 \|\mathcal{P}_{T^\perp} (H_{\Omega^c})\|_F & \le 2 \|H_\Omega\|_* \\
  \label{eq:PTpHOc}
  & \le 2\sqrt{n} \|H_\Omega\|_F \le 4\sqrt{n} \delta,
\end{align}
where the second inequality follows from the Cauchy-Schwarz
inequality, and the last from \eqref{eq:tube}.

To develop a bound on $\|\mathcal{P}_T(H_\Omega)\|_F$, observe that the assumption
$\mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T \succeq \frac{p}{2} \mathcal{I}$ together with $\mathcal{P}_T^2 = \mathcal{P}_T$,
$\mathcal{P}_\Omega^2 = \mathcal{P}_\Omega$ give
\begin{align*}
  \|\mathcal{P}_\Omega \mathcal{P}_T (H_{\Omega^c})\|^2_F & = \<\mathcal{P}_\Omega \mathcal{P}_T (H_{\Omega^c}), \mathcal{P}_\Omega \mathcal{P}_T (H_{\Omega^c})\> \\
  & = \<\mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T(H_{\Omega^c}), \mathcal{P}_T(H_{\Omega^c})\> \\
  & \ge \frac{p}{2} \| \mathcal{P}_T(H_{\Omega^c})\|_F^2.
\end{align*}
But since $\mathcal{P}_\Omega(H_{\Omega^c}) = 0 = \mathcal{P}_\Omega\mathcal{P}_T(H_{\Omega^c}) + \mathcal{P}_\Omega\mathcal{P}_{T^\perp}(H_{\Omega^c})$, we have
\begin{align*}
\|\mathcal{P}_\Omega \mathcal{P}_T (H_{\Omega^c})\|_F  & = \|\mathcal{P}_\Omega \mathcal{P}_{T^\perp} (H_{\Omega^c})\|_F \\
& \le \|\mathcal{P}_{T^\perp}(H_{\Omega^c})\|_F.
\end{align*}
Hence, the last two inequalities give
\begin{equation}
\label{eq:PTHOc}
  \|\mathcal{P}_T(H_{\Omega^c})\|^2_F \le \frac{2}{p}  \|\mathcal{P}_\Omega \mathcal{P}_T (H_{\Omega^c})\|^2_F \le  \frac{2}{p}  \, \|\mathcal{P}_{T^\perp}(H_{\Omega^c})\|^2_F.
\end{equation}
As a consequence of this and \eqref{eq:pythagoras}, we have
\begin{equation*}
  \label{eq:HOc}
  \|H_{\Omega^c}\|_F^2 \le \Bigl(\frac{2}{p}+1\Bigr)  \|\mathcal{P}_{T^\perp}(H_{\Omega^c})\|_F^2.
\end{equation*}
The theorem then follows from this inequality together with \eqref{eq:PTpHOc}.

\subsection{Comparison with an oracle}
\label{sec:oracle}

We would like to return to discussing the best possible accuracy one
could ever hope for.  For simplicity, assume that $n_1 = n_2 =
n$, and suppose that we have an oracle informing us about $T$. In many
ways, going back to the discussion from Section \ref{sec:T}, this is
analogous to giving away the support of the signal in compressed
sensing \cite{DS}. With this precious information, we would know that
$M$ lives in a linear space of dimension $2nr - r^2$ and would
probably solve the problem by the method of least squares:
\begin{equation}
  \label{eqn:LS}
  \begin{array}{ll}
    \textrm{minimize}   & \quad \|\mathcal{P}_\Omega(X) - \mathcal{P}_\Omega(Y)\|_F\\
    \textrm{subject to} & \quad X \in T.
 \end{array}
\end{equation}
That is, we would find the matrix in $T$, which best fits the data in a
least-squares sense. Let $\mathcal{A}: T \rightarrow \Omega$ (we abuse
notations and let $\Omega$ be the range of $\mathcal{P}_\Omega$) defined by
$\mathcal{A} := \mathcal{P}_\Omega \mathcal{P}_T$. Then assuming that the operator $\mathcal{A}^*\mathcal{A} =
\mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T$ mapping $T$ onto $T$ is invertible (which is the case
under the hypotheses of Theorem \ref{teo:stable}), the least-squares
solution is given by
\begin{align}
\nonumber
M^{\text{Oracle}} & := (\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Y) \\
\label{eq:ls}
& = M + (\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Z).
\end{align}
Hence,
\[
\|M^{\text{Oracle}} - M\|_F = \|(\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Z)\|_F.
\]
Let $Z'$ be the minimal (normalized) eigenvector of $\mathcal{A}^* \mathcal{A}$ with
minimum eigenvalue $\lambda_{\text{min}}$, and set $Z = \delta
\lambda_{\text{min}}^{-1/2}\mathcal{A}(Z')$ (note that by definition $\mathcal{P}_\Omega(Z) =
Z$ since $Z$ is in the range of $\mathcal{A}$). By construction, $\|Z\|_F =
\delta$, and
\[
\|(\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Z)\|_F = \lambda_{\text{min}}^{-1/2} \delta
\gtrsim p^{-1/2} \, \delta
\]
since by assumption, all the eigenvalues of $\mathcal{A}^*\mathcal{A} = \mathcal{P}_T \mathcal{P}_\Omega \mathcal{P}_T$
lie in the interval $[p/2, 3p/2]$. The matrix $Z$ defined above also
maximizes $\|(\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Z)\|_F$ among all matrices bounded
by $\delta$ and so the oracle achieves
\begin{equation}
  \label{eq:oracle1}
 \|M^{\text{Oracle}} - M\|_F \approx p^{-1/2} \delta
\end{equation}
with adversarial noise.  Consequently, our analysis looses a
$\sqrt{n}$ factor vis a vis an optimal bound that is achievable via
the help of an oracle.

The diligent reader may argue that the least-squares solution above
may not be of rank $r$ (it is at most of rank $2r$) and may thus argue
that this is not the strongest possible oracle.  However, as explained
below, if the oracle gave $T$ and $r$, then the best fit in $T$ of
rank $r$ would not do much better than \eqref{eq:oracle1}. In fact,
there is an elegant way to understand the significance of this oracle
which we now present. Consider a stronger oracle which reveals the row
space of the unknown matrix $M$ (and thus the rank of the
matrix). Then we would know that the unknown matrix is of the form
\[
M = M_C R^*,
\]
where $M_C$ is an $n \times r$ matrix, and $R$ is an $n \times r$
matrix whose columns form an orthobasis for the row space (which we
can build since the oracle gave us perfect information). We would then
fit the $nr$ unknown entries by the method of least squares and find
$X \in \mathbb{R}^{n \times r}$ minimizing
\[
\|\mathcal{P}_\Omega(XR^*) - \mathcal{P}_\Omega(Y)\|_F.
\]
Using our previous notations, the oracle gives away $T_0 \subset T$
where $T_0$ is the span of elements of the form $y v_k^*$, $k \in
[r]$, and is more precise. If $\mathcal{A}_0 : T_0 \rightarrow \Omega$ is
defined by $\mathcal{A}_0 := \mathcal{P}_\Omega \mathcal{P}_{T_0}$, then the
least-squares solution is now
\[
(\mathcal{A}_0^* \mathcal{A}_0)^{-1} \mathcal{A}_0^*(Y).
\]
Because all the eigenvalues of $\mathcal{A}_0^* \mathcal{A}_0$ belong to
$[\lambda_{\text{min}}(\mathcal{A}^* \mathcal{A}), \lambda_{\text{max}}(\mathcal{A}^* \mathcal{A})]$,
the previous analysis applies and this stronger oracle would also
achieve an error of size about $p^{-1/2}\delta$. In conclusion, when
all we know is $\|\mathcal{P}_\Omega(Z)\|_F \le \delta$, one cannot hope for a
root-mean squared error better than $p^{-1/2} \delta$.

Note that when the noise is stochastic, e.~g.~when $Z_{ij}$ is white
noise with standard deviation $\sigma$, the oracle gives an error
bound which is adaptive, and is smaller as the rank gets
smaller. Indeed, $\operatorname{\mathbb{E}} \|(\mathcal{A}^* \mathcal{A})^{-1} \mathcal{A}^*(Z)\|^2_F$ is equal to
\begin{equation}
 \sigma^2 \operatorname{trace}((\mathcal{A}^* \mathcal{A})^{-1}) \approx \frac{2nr - r^2}{p} \sigma^2
\approx \frac{2nr}{p} \sigma^2 \label{eq:oracle2},
\end{equation}
since all the $2nr-r^2$ eigenvalues of $(\mathcal{A}^* \mathcal{A})^{-1}$ are just
about equal to $p^{-1}$. When $nr \ll m$, this is better than
\eqref{eq:oracle1}.

\section{Numerical Experiments}
\label{sec:numerical}

We have seen that matrix completion is stable amid noise.  To
emphasize the practical nature of this result, a series of numerical
matrix completion experiments were run with noisy data.  To be
precise, for several values of the dimension $n$ (our first
experiments concern $n \times n$ matrices), the rank $r$, and the
fraction of observed entries $p = m/n^2$, the following numerical
simulations were repeated 20 times, and the errors averaged. A
rank-$r$ matrix $M$ is created as the product of two rectangular
matrices, $M=M_L M_R^*$, where the entries of $M_L, M_R \in \mathbb{R}^{n
  \times r}$ are iid $N(0, \sigma_n^2 := 20/\sqrt{n})$\footnote{The value of
  $\sigma_n$ is rather arbitrary.  Here, it is set so that the
  singular values of $M$ are quite larger than the singular values of
  $\mathcal{P}_\Omega(Z)$ so that $M$ can be distinguished from the null matrix.
  Having said that, note that for large $n$ and small $r$, the entries
  of $M$ are much smaller than those of the noise, and thus the signal
  appears to be completely buried in noise.}.  The sampled set
$\Omega$ is picked uniformly at random among all sets with $m$
entries.  The observations $\mathcal{P}_\Omega(Y)$ are corrupted by noise as in
\eqref{eq:noisy}, where $\{Z_{ij}\}$ is iid $N(0, \sigma^2)$; here, we
take $\sigma = 1$.  Lastly, $\hat{M}$ is recovered as the solution to
\eqref{eq:fpc} below.

For a peek at the results, consider Table \ref{tab:firstLook}.
\begin{table}
\begin{center}
\begin{tabular}{|c|cccc|}
\hline
$n$ & $100$ & $200$ & $500$ & $1000$\\
\hline
RMS error & $.99$ & $.61$ & $.34$ & $.24$\\
\hline
\end{tabular}
\end{center}
\caption{RMS error ($\|\hat M-M\|_F/n$) as a function of $n$ when subsampling 20\% of an $n \times n$ matrix of rank two. Each RMS error is averaged over 20 experiments.}
\label{tab:firstLook}
\end{table}
The RMS error defined as $\|\hat{M} - M\|_F/n$, measures the root-mean
squared error per entry.  From the table, one can see that even though
each entry is corrupted by noise with variance 1, when $M$ is a 1000
by 1000 matrix, the RMS error per entry is .24.  To see the
significance of this, suppose one had the chance to see {\em all} the
entries of the noisy matrix $Y = M + Z$.  Naively accepting $Y$ as an
estimate of $M$ would lead to an expected MS error of $\operatorname{\mathbb{E}} \|Y -
M\|_F^2/n^2 = \operatorname{\mathbb{E}} \|Z\|_F^2/n^2 = 1$, whereas the RMS error achieved
from only viewing 20\% of the entries is $\|\hat{M} - M\|_F^2/n^2 =
.24^2 = .0576$ when solving the SDP (\ref{eq:fpc})! Not only are we
guessing accurately the entries we have not seen, but we also
``denoise'' those we have seen.

In order to stably recover $M$ from a fraction of noisy entries,
the following regularized nuclear norm minimization problem was solved
using the FPC algorithm from \cite{Ma08},
\begin{equation}
\label{eq:fpc}
\textrm{minimize}   \quad
\frac{1}{2} \|\mathcal{P}_\Omega(X - Y)\|_F^2 + \mu \|X\|_*.
\end{equation}
It is a standard duality result that \eqref{eq:fpc} is equivalent to
\eqref{eq:lasso}, for some value of $\mu$, and thus one could use
\eqref{eq:fpc} to solve \eqref{eq:lasso} by searching for the value of
$\mu(\delta)$ giving $\|\mathcal{P}_\Omega(\hat{M} - Y)\|_F = \delta$ (assuming
$\|\mathcal{P}_\Omega(Y)\|_F > \delta$).  We use \eqref{eq:fpc} because it works well
in practice, and because the FPC algorithm solves \eqref{eq:fpc}
nicely and accurately.
We also remark that a variation on our stability proof could also give
a stable error bound when using the SDP \eqref{eq:fpc}.

It is vital to choose a suitable value of $\mu$, which we do with the
following heuristic argument: first, simplifying to the case when
$\Omega$ is the set of all elements of the matrix, note that the
solution of \eqref{eq:fpc} is equal to $Y$ but with singular values
shifted towards zero by $\mu$ (soft-thresholding), as can be seen from
the optimality conditions of Section \ref{sec:exact} by means of
subgradients, or see \cite{Cai08}.  When $\Omega$ is not the entire
set, the solution is no longer exactly a soft-thresholded version of
$Y$, but experimentally, it is generally close.  Thus, we want to pick
$\mu$ large enough to threshold away the noise (keep the variance
low), and small enough not to overshrink the original matrix (keep the
bias low).  To this end, $\mu$ is set to be the smallest possible
value such that if $M = 0$ and $Y = Z$, then it is likely that the
minimizer of \eqref{eq:fpc} satisfies $\hat{M} = 0$.  It can be seen
that the solution to (\ref{eq:fpc}) is $\hat{M} = 0$ if $\|\mathcal{P}_\Omega(Y)\|
\leq \mu$ (once again, check the subgradient or \cite{Cai08}).  Then
the question is: what is $\|\mathcal{P}_\Omega(Z)\|$?  If we make a nonessential
change in the way $\Omega$ is sampled, then the answer follows from
random matrix theory.  Rather than picking $\Omega$ uniformly at
random, choose $\Omega$ by selecting each entry with probability $p$,
independently of the others.  With this modification, each entry of
$\mathcal{P}_\Omega(Z)$ is iid with variance $p \sigma^2$.  Then if $Z \in
\mathbb{R}^{n\times n}$, it is known that
$n^{-1/2}\, \|\mathcal{P}_\Omega(Z)\| \rightarrow \sqrt{2p} \sigma$, almost surely as
$n \rightarrow \infty$.  Thus we pick $\mu = \sqrt{2np}\sigma$, where
$p = m/n^2$.  In practice, this value of $\mu$ seems to work very well
for square matrices. For $n_1 \times n_2$ matrices, based on the same
considerations, the proposal is $\mu = (\sqrt{n_1} +
\sqrt{n_2})\sqrt{p} \sigma$ with $p = m/(n_1n_2)$.

In order to interpret our numerical results, they are compared to
those achieved by the oracle, see Section \ref{sec:oracle}.  To this
end, Figure \ref{fig:errors} plots three curves for varying values of
$n, p,$ and $r$: 1) the RMS error introduced above, 2) the RMS error
achievable when the oracle reveals $T$, and the problem is solved
using least squares, 3) the estimated oracle root expected MS error
derived in Section \ref{sec:oracle}, i.e.~$\sqrt{\text{df}/[n^2p]} =
\sqrt{\text{df}/m}$, where $\text{df} = r(2n-r)$.  In our experiments,
as $n$ and $m/\text{df}$ increased, with $r=2$, the RMS error of the
nuclear norm problem appeared to be fit very well by $1.68\,
\sqrt{\text{df}/m}$.  Thus, to compare the oracle error to the actual
recovered error, we plotted the oracle errors times 1.68.  We also
note that in our experiments, the RMS error was never greater than
$2.25\, \sqrt{\text{df}/m}$.
\begin{figure}
\begin{center}
\begin{tabular}{c}
  \includegraphics[scale=0.464]{samplingRateChanging.pdf}\\
  \includegraphics[scale=0.464]{dimensionChanging.pdf}\\
  \includegraphics[scale=0.49]{rankChanging.pdf}
\end{tabular}
\end{center}
\caption{\small Comparison between the recovery error, the oracle
  error times 1.68, and the estimated oracle error times 1.68.  Each
  point on the plot corresponds to an average over 20 trials. Top: in
  this experiment, $n = 600, r = 2$ and $p$ varies. The x-axis is the
  number of measurements per degree of freedom (df).  Middle: $n$
  varies whereas $r = 2$, $p = .2$.  Bottom: $n = 600$, $r$ varies and
  $p = .2$.}
\label{fig:errors}
\end{figure}

{\em No one can predict the weather.}  We conclude the numerical
section with a real world example.  We retrieved from the website
\cite{temp} a $366 \times 1472$ matrix whose entries are daily average
temperatures at 1472 different weather stations throughout the world
in 2008.  Checking its SVD reveals that this is an approximately low
rank matrix as expected.  In fact, letting $M$ be the temperature
matrix, and calling $M_2$ the matrix created by truncating the SVD
after the top two singular values gives $\|M_2\|_F/\|M\|_F = .9927$.

To test the performance of our matrix completion algorithm, we
subsampled 30\% of $M$ and then recovered an estimate, $\hat{M}$,
using (\ref{eq:fpc}).  Note that this is a much different problem than
those proposed earlier in this section.  Here, we attempt to recover a
matrix that is not exactly low rank, but only approximately. The
solution gives a relative error of $\|\hat{M} - M\|_F/\|M\|_F = .166$.
For comparison\footnote{The number 2 is somewhat arbitrary here,
  although we picked it because there is a large drop-off in the size
  of the singular values after the second.  If, for example, $M_{10}$
  is the best rank-10 approximation, then $\|M_{10} - M\|_F/\|M\|_F =
  .081$.}, exact knowledge of the best rank-2 approximation achieves
$\|M_2 - M\|_F/\|M\|_F = .121$.  Here $\mu$ has been selected to give
a good cross-validated error and is about 535.

\section{Discussion}
\label{sec:discussion}

This paper reviewed and developed some new results about matrix
completion. By and large, low-rank matrix recovery is a field in
complete infancy abounding with interesting and open questions, and
if the recent avalanche of results in compressed sensing is any
indication, it is likely that this field will experience tremendous
growth in the next few years.

At an information theoretic level, one would like to know whether one
can recover low-rank matrices from a few general linear functionals,
i.~e.~from $\mathcal{A}(M) = b$, where $\mathcal{A}$ is a linear map from $\mathbb{R}^{n_1
  \times n_2} \rightarrow \mathbb{R}^m$. In this direction, we would like to single
out the original result of Recht, Fazel and Parrilo \cite{Recht07} who
showed---by leveraging the techniques and proofs from the compressed
sensing literature---that if each measurement is of the form $\<A_k,
X\>$, where $A_k$ is an independent array of iid Gaussian variables (a
la compressed sensing), then the nuclear norm heuristics recovers
rank-$r$ matrices from on the order of $nr \log n$ such randomized
measurements.

At a computational level, one would like to have available a suite of
efficient algorithms for minimizing the nuclear norm under convex
constraints and, in general, for finding low-rank matrices obeying
convex constraints. Algorithms with impressive performance in some
situations have already been proposed \cite{Cai08,Ma08} but the
computational challenges of solving problems with millions if not
billions of unknowns obviously still require much research.

\subsection*{Acknowledgements}
E.~C. is supported by ONR grants N00014-09-1-0469 and N00014-08-1-0749
and by the Waterman Award from NSF. E.~C. would like to thank Terence
Tao and Stephen Becker for some very helpful discussions.

\small
\bibliographystyle{plain}


text:
\section{Introduction}
The uniform regularity defined from the H\"older spaces $C^\alpha(\R^d)$ is one of the most popular concepts for the uniform regularity. It has been introduced to study smoothness properties of functions such as the Weierstra{\ss} function (see \cite{har:16}). Indeed, many ``historical'' functions share the same property (see \cite{jaf-nic:09}): there exist $H\in (0,1)$ and a constant $C>0$ such that the function $f$ satisfies on some interval $I$,
\begin{equation}\label{eq:unif rir1}
\forall x,y\in I,\, |f(x)-f(y)| \le C |x-y|^H\;,
\end{equation}
and
\begin{equation}\label{eq:unif rir2}
\forall x,y\in I, \sup_{(u,v)\in [x,y]^2}|f(x)-f(y)| \ge \frac{1}{C} |x-y|^H\;.
\end{equation}
It has been shown in \cite{clanic:pre} that this behavior is the typical behavior of the functions belonging to $C^H(\R^d)$, in the sense of prevalence (the notion of prevalence will be defined in the sequel, see section~\ref{subsec:prev}). In other words, almost every function of $C^H(\R^d)$ satisfies Relations~(\ref{eq:unif rir1}) and~(\ref{eq:unif rir2}).

However, in many cases, the functions do not satisfy Relations~(\ref{eq:unif rir1}) and~(\ref{eq:unif rir2}). It is in particular the case of the so-called multifractal functions (see Definition~\ref{def:f multifrac}), originally introduced in the context of turbulence and now used in many fields of science (see e.g.\ \cite{abr:02,arn:02,hal:86,jaf:01,sre:91}). It can be shown that in several functional spaces, almost every function (in the sense of prevalence) is multifractal (see \cite{fra:06,aub:07}).

In this paper, we aim at investigating the typical irregularity properties of the elements of the $S^\nu$ spaces. These functional spaces, defined in \cite{jaf:snu,aub:06}, give rise to an efficient multifractal formalism (see section~\ref{sec:multifrac models}), i.e.\ an heuristic method to study the pointwise regularity of a function from a global point of view. It has been shown in \cite{aub:07} that almost every element of $S^\nu$ is multifractal. We show here that, although they are multifractal, the elements of $S^\nu$ also satisfy almost surely a weak uniform irregularity property. To this end, we introduce a concept of weak uniform irregularity, define the irregularity exponent $\uhl(x_0)$ of a function at a given point $x_0$ and prove that, in the sense of prevalence, there exists $\alpha$ (depending on $S^\nu$) such that almost every function of $S^\nu$ satisfy
\[
 \uhl(x)=\alpha,
\]
for any $x$.

The paper is organized as follows. In the next section, we recall some definitions about the multifractal analysis and the $S^\nu$ spaces. Next, we define the local irregularity exponent. To prove our main result, we will need wavelet criteria for the irregularity; these are stated in Section~\ref{sec:criteria}. The prevalent result is obtained in the last section.

\section{Multifractal models}\label{sec:multifrac models}
The multifractal analysis aims to study the smoothness of very irregular signals. For such a function, it is meaningless to try to characterize its regularity at a given point, since the pointwise regularity can abruptly change. One rather tries to determine the so-called spectrum of singularities, which gives the size of the set of points that share the same pointwise regularity. We first have to precise what is meant by ``pointwise regularity'' and ``size of set''. The $S^\nu$ spaces have been introduced in order to provide an efficient multifractal formalism, i.e.\ a method that allows the computation of the multifractal spectrum in many practical cases. Although this technique does not always lead to the right spectrum, it has been shown that the $S^\nu$-based multifractal formalism gives the right answer for almost every element of $S^\nu$. Here the term ``almost every'' has to be clearly stated, since one can not use the usual Lebesgue measure for the infinite dimensional settings. Finally, we introduce another index of regularity, called the local irregularity exponent.

\subsection{Pointwise regularity, Hausdorff dimension and multifractal spectrum}
The notion of the pointwise regularity which we will use here is based on the characterization of the H\"older spaces $C^\alpha(x_0)$.
\BDef
Let $x\in\R^d$ and $\alpha>0$. A locally bounded function $f:\R^d\to \C$ belongs to $C^\alpha(x_0)$ if there exist $C>0$ and a polynomial $P$ of degree strictly lower than $\alpha$ such that, in a neighborhood of $x_0$,
\[
 |f(x)-P(x-x_0)| \le C |x-x_0|^\alpha.
\]
The H\"older exponent of $f$ at $x_0$ is the quantity
\[
 \h(x_0)=\sup\{\alpha>0: f\in C^\alpha(x_0)\}.
\]
\EDef

The multifractal analysis provides a description of the collection of the H\"older exponents of a function by way of the multifractal spectrum (also called the singularity spectrum), which associates to a value $h$ the size of the set of points for which the H\"older exponent is $h$. By size, one usually means Hausdorff dimension; this notion of dimension is usually preferred because it relies on a measure. We will only give the necessary definitions; the interested reader is referred to e.g.\ \cite{fal:90,mat:95}.
\BDef
Let $S$ be a Borelian subset of $\R^d$ and $\Gamma_\epsilon(S)$ be the collection of all the countable $\epsilon$-coverings of $S$, i.e.\ the collection of all the countable coverings of $S$ by sets whose diameter is lower than $\epsilon$. The $\delta$-dimensional Hausdorff measure of $S$ is
\[
 m^\delta(S)=\lim_{\epsilon\to 0} \inf_{(S_j)_j \in \Gamma_\epsilon(S)} \sum_j |S_j|^\delta,
\]
where $|S_j|$ denotes the diameter of the set $S_j$.
\EDef
It is easy to check that if $m^{\delta_0}(S)$ is finite, then $m^\delta(S)=\infty$ if $\delta<\delta_0$ and $m^\delta(S)=0$ if $\delta>\delta_0$. We are then naturally led to the following definition.
\BDef
The Hausdorff dimension $\dim S$ of a non-empty Borelian subset $S$ of $\R^d$ is given by
\[
 \dim S=\inf\{\delta: m^\delta(S)=0\}.
\]
One sets $\dim \emptyset=-\infty$.
\EDef
If $S$ is empty or uncountable, one has $\dim S=\sup\{\delta: m^\delta(S)=\infty\}$.
We are now able to introduce the multifractal spectrum of a function.
\BDef
The multifractal spectrum of a locally bounded function $f:\R^d\to \C$ is the application
\[
 d : (0,\infty]\to [-\infty,d] \quad h\mapsto \dim\{x\in \R^d: \h(x)=h\}.
\]
\EDef
Finally, let us introduce some usual denominations.
\BDef\label{def:f multifrac}
A function is called multifractal if the associated multifractal spectrum takes more than one real value on a support with non-zero Hausdorff dimension. A function that is not multifractal is a monofractal function. If the spectrum only takes one value, the function is said to be monoH\"older.
\EDef

\subsection{Bases of wavelets and $S^\nu$ spaces}
One of the remarkable aspects of the wavelets is that they provide bases of the space $L^2(\R^d)$. Historically, the first orthonormal wavelet basis is the Haar basis, constructed long before the introduction of the term ``wavelet''. In \cite{jaf:04}, it is shown that, under some suitable conditions, the multifractal spectrum of a function can be estimated from its wavelet coefficients. The $S^\nu$ spaces were introduced in \cite{jaf:snu} to improve the classical wavelet-based multifractal formalism. The $S^\nu$ spaces are closely related to the Besov spaces.

Let us briefly recall some definitions and notations (for more precisions, see e.g.\ \cite{mey:90,dau:92,mal:98}). Under some general assumptions, there exist a function $\phi$ and $2^d-1$ functions $(\psi^{(i)})_{1\le i < 2^d}$ called wavelets such that
\[
 \{\phi(x-k): k\in \Z^d\} \cup \{\psi^{(i)}(2^j-k): 1\le i<2^d, k\in \Z^d, j\in \N \}
\]
form a basis of $L^2(\R^d)$. A function $f\in L^2(\R^d)$ can be decomposed as follows,
\[
 f= \sum_{k\in \Z^d} C_k \phi(\cdot -k) + \sum_{j=1}^\infty \sum_{k\in\Z^d} \sum_{i=1}^{2^d-1} c_{j,k}^{(i)} \psi^{(i)} (2^j \cdot -k),
\]
where
\[
 C_k= \int_{\R^d} f(x) \phi(x-k) \,dx
\]
and
\begin{equation}\label{eq:cjki}
 c_{j,k}^{(i)} =  2^{dj} \int_{\R^d} f(x) \psi^{(i)} (2^j x -k) \,dx.
\end{equation}
Let us remark that we do not choose the (usual) $L^2$ normalization for the wavelets, but rather an $L^\infty$ normalization, which is better fitted to the study of the H\"olderian regularity. Expressions such as (\ref{eq:cjki}) can make sense in more general settings (e.g.\ if $f$ is a distribution). Hereafter, we will assume that the wavelets belong to $C^\gamma(\R^d)$ with $\gamma\ge\alpha+1$, and that the functions $\{\partial^s \phi\}_{|s|\le\gamma}$, $\{\partial^s \psi\}_{|s|\le\gamma}$ have fast decay. Moreover, for the sake of simplicity, when dealing with the $S^\nu$ spaces, we will suppose that the application $f$ is defined on the torus $\T^d=\R^d/\Z^d$. Let
\[
 \Lambda=\left\{(i,j,k): 1\le i<2^d, j\in \N, k\in\{0,\ldots,2^j-1\}^d\right\}\;.
\]
If $(i,j,k)\in \Lambda$, the periodized
\[
 \psi^{(i)}_{j,k} = \sum_{l\in \Z^d} \psi \big( 2^j(\cdot -l) -k \big)
\]
form a basis of the one-periodic functions in $L^2([0,1]^d)$. We will denote $(c_{j,k}^{(i)})_{(i,j,k)\in\Lambda}$ or $(c_\lambda)_{\lambda\in\Lambda}$ the wavelet coefficients of a function in $L^2([0,1]^d)$.

Let us now introduce the $S^\nu$ spaces.
\BDef
For a sequence $c=(c_\lambda)_{\lambda\in\Lambda}$, $C>0$ and $\alpha\in\R$, we define
\[
 E_j(C,\alpha)[c]= \{(i,k): |c_{j,k}^{(i)}\ge C 2^{-j\alpha}\}.
\]
The wavelet profile $\nu_c$ of $c$ is defined as
\[
 \nu_c(\alpha)= \lim_{\epsilon\to 0^+} \limsup_{j\to\infty} \frac{\log_2 \#E_j(1,\alpha+\epsilon)[c]}{j}\;,
\]
with $\alpha\in\R$. If $c$ represents the wavelet coefficients of a function $f$, one sets $E_j(C,\alpha)[f]=E_j(C,\alpha)[c]$ and $\nu_f=\nu_c$.
\EDef
Clearly, $\nu_c$ is non-decreasing, right-continuous and non-negative (lower than $d$) when not equal to  $-\infty$. It gives, in some way, the asymptotic behavior of the number of coefficients of $c$ that have a given order of magnitude.
\BDef\label{def:snu}
Let $\nu:\R\to \{-\infty\} \cup [0,d]$ be a non-decreasing, right-continuous function such that there exists $\alpha_0$ for which $\nu(\alpha)=-\infty$ if $\alpha<\alpha_0$ and $\nu(\alpha)\in [0,d]$ otherwise. A sequence distribution $f$ belongs to $S^\nu$ if its wavelet coefficients satisfy $\nu_f(\alpha)\le \nu(\alpha)$ for any $\alpha\in\R$.
\EDef
These spaces are robust, in the sense that their definition does not depend on the choice of the wavelet basis (see \cite{jaf:snu}). Roughly speaking, a function belongs to $S^\nu$ if for each scale $j$ and every $\alpha\in \R$, there are about $2^{\nu(\alpha)j}$ coefficients $c_{j,k}^{(i)}$ that are larger than $2^{-\alpha j}$. The following definition is equivalent to the preceding one (see \cite{aub:06}).
\BDef
If $\nu$ is a function as given in Definition~\ref{def:snu}, $f$ belongs to $S^\nu$ if for any $\alpha\in\R$, $\epsilon>0$ and $C>0$, there exists $J$ such that $j\ge J$ implies
\[
 \#E_j(C,\alpha)[f] \le 2^{(\nu(\alpha)+\epsilon)j}.
\]
\EDef

A topological framework for the spaces $S^\nu$ will also be needed (further details can be found in \cite{aub:06,aub:07}). The ancillary spaces are useful to obtain a structure of complete metric space on $S^\nu$.
\BDef
Let $m,n\in\N$; $f$ belongs to $E_{m,n}$ if there exist $C>0$ such that
\begin{equation}\label{eq:anc sp}
 \# E_j(C,\alpha_m)[f]\le C 2^{\nu(\alpha_m)+\epsilon_n)j},
\end{equation}
for any $j$, where $(\alpha_m)_m$ is any dense sequence in $\R$ and $(\epsilon_n)_n$ is decreasing to zero.
\EDef
If for $f\in E_{m,n}$, the infimum of the constants $C$ satisfying the inequality (\ref{eq:anc sp}) is noted $d_{m,n}(f,0)$, the distance $d_{m,n}(f,g)=d_{m,n}(f-g,0)$ makes $(E_{m,n},d_{m,n})$ a metric space. It can be shown that $S^\nu=\cap_{m,n} E_{m,n}$ and that with the distance
\[
 d(f,g)= \sum_{m,n\ge 0} 2^{-m-n} \frac{d_{m,n}(f,g)}{1+d_{m,n}(f,g)},
\]
the space $(S^\nu,d)$ is a complete separable metric space. The distance $d$ may depend on the sequences chosen in (\ref{eq:anc sp}), but the induced topology does not. The Borel $\sigma$-algebra relative to this topology will be denoted $\B(S^\nu)$.

\subsection{Prevalence of multifractal functions in $S^\nu$}\label{subsec:prev}
In a finite dimensional space, a property ``holds almost everywhere'' if the set of points for which this property is not satisfied vanishes for the Lebesgue measure. The Lebesgue measure has a preponderant role, as there is no other $\sigma$-finite translation invariant measure. Unfortunately, there is such measure in the infinite dimensional Banach spaces. The notion of prevalence provides the analogue of ``Lebesgue measure zero'' in complete metric vector spaces.

In \cite{chris:72}, to recover the notion of ``almost every'' in infinite vector spaces, a well-known characterization of Lebesgue measure zero subsets of $\R^d$ is generalized: In $\R^d$, a Borel set $B$ has Lebesgue measure zero if and only if there exists a compactly supported probability measure $\mu$ such that $\mu(B+x)=0$ for any $x\in\R^d$. This characterization can be turned into a definition in more general settings and leads to the concept of Haar-null set, which provides the analogue of ``Lebesgue measure zero'' set for infinite dimensional spaces.
\BDef\label{def:harr-null}
Let $E$ be a complete metric vector space. A Borel set $B\subset E$ is Haar-null if there exists a Borel probability measure, strictly positive on some compact set $K\subset E$ such that $\mu(B+x)=0$ for any $x\in E$. A subset of $E$ is Haar-null if it is included in a Haar-null Borel subset of $E$. The complement of a Haar-null set is called a prevalent set.
\EDef

In \cite{aub:07}, the prevalent behavior of almost every function of $S^\nu$ has been studied and it has been proved that almost every function of $S^\nu$ is multifractal. More precisely, an upper bound of the spectrum $d$ of any $f\in S^\nu$ is first given: if $\alpha_\text{max}=\inf_{h\ge \alpha_0} \{h/\nu(h)\}$ and
\[
 d_\nu(h)=\left\{\begin{tabular}{ll}
                  $h \sup_{h'\in (0,h]} \{\nu(h')/h'\}$ & if $h\le \alpha_\text{max}$ \\
                  $1$ & otherwise
                 \end{tabular}\right.,
\]
one has, for all $f\in S^\nu$ and $h\in \R$, $d(h)\le d_\nu(h)$. Then it is shown that the sets
\[
 \{f\in S^\nu: \text{$d(h)=d_\nu(h)$ if $h\le \alpha_\text{max}$ and $d(h)=-\infty$ otherwise}\}
\]
and
\[
 \{f\in S^\nu: \text{the pointwise regularity is almost everywhere $\alpha_\text{max}$}\}
\]
are prevalent. The ``typical elements'' (in the sense of the prevalence) of $S^\nu$ are thus multifractal and do not satisfy the classical law of the iterated logarithm almost everywhere.

\subsection{Local regularity exponents}
We introduce here another notion of local regularity, which will be used to state that a weak irregularity condition is satisfied for almost every multifractal function of $S^\nu$. To this end, we first need to recall different concepts of global regularity, based on the global H\"older regularity.

If $\Omega$ is an open subset of $\R^d$, for any $h\in\R^d$, we will denote by $\Omega_h$ the set
\[
 \Omega_h= \{ x\in\R^d : [x,([\alpha]+1)h]\subset \Omega\},
\]
where the value $\alpha>0$ will be implied by the context and $[\alpha]$ denotes the greatest integer lower than $\alpha$. We will need the classical notion of finite difference.
\BDef
Let $x,h\in\R^d$ and $f:\R^d\to \C$; the first order difference of $f$ is $\Delta_h^1 f(x)= f(x+h)-f(x)$. For $n\ge 2$, the difference of order $n$ is defined by
\[
 \Delta_h^n f(x)= \Delta_h^{n-1} \Delta_h^1 f (x).
\]
\EDef
We can now introduce the H\"older spaces $C^\alpha(\Omega)$.
\BDef
Let $\Omega$ be an open subset of $\R^d$ and $\alpha>0$; a bounded function $f$ defined on a subset of $\R^d$ belongs to $C^\alpha(\Omega)$ if there exist $C,r_0>0$ such that for any $r\le r_0$,
\[
 \sup_{|h|\le r} \|\Delta_h^{[\alpha]+1} f (x) \|_{L^\infty(\Omega_h)} \le C r^\alpha.
\]
The function $f$ is said to be uniformly H\"olderian on $\Omega$ if for some $\alpha>0$, $f$ belongs to $C^\alpha(\Omega)$.
\EDef

We will also need a notion of uniform irregularity.
\BDef
Let $\Omega$ be an open subset of $\R^d$, $\alpha>0$ and $\beta\in\R$; a bounded function $f$ defined on a subset of $\R^d$ belongs to $I^\alpha (\Omega)$ if there exist $C,r_0>0$ such that for any $r\le r_0$,
\[
 \sup_{|h|\le r} \|\Delta_h^{[\alpha]+1} f (x) \|_{L^\infty(\Omega_h)} \ge C r^\alpha.
\]
A function that belongs to $I^\alpha(\Omega)$ is said to be uniformly irregular with exponent $\alpha$.
\EDef
Let us remark that the statement $f\in I^\alpha(\Omega)$ is not equivalent to $f\notin C^\alpha(\Omega)$. In the latter case, for any $C>0$, there exists a sequence $(r_n)_n$ (depending on $C)$ decreasing to zero for which
\[
 \sup_{|h|\le r_n} \|\Delta_h^{[\alpha]+1} f\|_{L^\infty(\Omega_h)} \ge C r_n^\alpha.
\]
We are thus naturally led to the following definition.
\BDef
Let $\Omega$ be an open subset of $\R^d$, $\alpha>0$ and $\beta\in\R$; a bounded function belong to $C^\alpha_w (\Omega)$ if $f$ is defined on $\Omega$ and if for any $C>0$, there exists a decreasing sequence $(r_n)_n$ decreasing to zero such that
\[
 \sup_{|h|\le r_n} \|\Delta_h^{[\alpha]+1} f \|_{L^\infty(\Omega)} \le C r_n^\alpha,
\]
for any $n\in\N$. The set $C^\alpha_{\beta,w}(\Omega)$ is simply denoted $C^\alpha_w(\Omega)$. A function that belong to $C^\alpha_w(\Omega)$ is said to be weakly uniformly H\"older with exponent $\alpha$ on $\Omega$.
\EDef
\BDef
The upper uniform H\"older exponent of a weakly uniformly H\"older function $f$ on an open set $\Omega$ is defined as
\[
 \uhl(\Omega) = \sup\{ \alpha>0: f\in C^\alpha_w(\Omega)\}.
\]
\EDef

We now define the local irregular exponent, using the same approach as in \cite{lev:02}.
\BDef
A sequence $(\Omega_n)_n$ of open subsets of $\R^d$ is decreasing to $x_0\in\R^d$ if
\begin{itemize}
 \item $m<n$ implies $\Omega_n \subset \Omega_m$,
 \item $|\Omega_n|\to 0$ as $n\to \infty$,
 \item $\cap_n \Omega_n= \{x_0\}$.
\end{itemize}
\EDef
The following lemma is needed.
\BLem
If $(\Omega_n)_n$ and $(\Omega'_n)_n$ are two sequences of open sets that decrease to $x_0$, then
\[
 \sup_{n\in\N} \{\uhl(\Omega_n)\}
 = \sup_{n\in\N} \{\uhl(\Omega'_n)\}.
\]
\ELem
\BProof
Let us suppose that $\sup_{n\in\N} \{\uhl(\Omega_n)\} > \sup_{n\in\N} \{\uhl(\Omega'_n)\}$. There exists an index $n_1$ such that $\uhl(\Omega_{n_1})> \sup_{n\in\N} \{\uhl(\Omega'_n)\}$. Now let $r>0$ be such that $B(x_0,r)\subset \Omega_{n_1}$; since $(\Omega_n')_n$ is decreasing to $x_0$, there exists an index $n_2$ such that $\Omega'_{n_2}\subset B(x_0,r)$. One thus have
\[
 \uhl(\Omega'_{n_2}) \ge \uhl(\Omega_{n_1}) > \sup_{n\in\N} \{\uhl(\Omega'_n)\},
\]
which leads to a contradiction.
\EProof
\BDef
If $f$ is a bounded function, the local irregularity exponent of $f$ at $x_0$ is
\[
 \uhl(x_0)= \sup_n\{ \uhl(\Omega_n)\},
\]
where $(\Omega_n)_n$ is a sequence of open sets decreasing to $x_0$.
\EDef

\section{Wavelet criteria for the uniform irregularity and characterization of the local irregularity exponent}\label{sec:criteria}
In this section, we first give necessary and sufficient conditions for a function to belong to $I^\alpha(\Omega)$. Next we characterize the local irregularity exponent in terms of wavelet coefficients.

\subsection{Wavelet criteria for the uniform irregularity}
In what follows, we will assume that the multiresolution analysis is compactly supported (see \cite{dau:88}). The following result is shown in \cite{jaf:04}: in $\R$, if the wavelet basis belongs to $C^M(\R)$, there exist a fast decaying function $\Psi_M$ such that $\psi=\Delta_{1/2}^M \Psi_M$. Furthermore, the function $\Psi_M$ can be picked compactly supported with support included in this of $\psi$. In $\R^d$, we will use the tensor product wavelet basis (see \cite{mey:90,dau:92}),
\[
 \psi^{(i)}(x)=\Psi^{(1)}(x_1) \cdots \Psi^{(d)}(x_d),
\]
where $\Psi^{(i)}$ ($i\in \{1,\ldots,d\}$) are either $\psi$ or $\phi$, but at least one of them must equal $\psi$. We will also use the following notations: given $j\in\N$, $\Omega$ an open subset of $\R^d$ and a family of wavelets $\psi^{(i)}_{j,k}$, we set
\[
 I_j=\{ (i,k): \supp{\psi^{(i)}_{j,k}} \subset \Omega\}
\]
and
\[
 \| c^{(\cdot)}_{j,\cdot} \|_{\ell^\infty(\Omega)}= \sup_{I_j} |c^{(i)}_{j,k}|.
\]

The uniform regularity of a function is related to the decay rate of its wavelet coefficients (see \cite{mey:90}). Let $f$ be a bounded function and $\alpha\in (0,1)$; $f$ belongs to $\dot{C}^\alpha(\Omega)$ (where $\dot{C}^\alpha(\Omega)$ denotes the homogeneous version of the H\"older space $C^\alpha(\Omega)$) if and only if there exists $C>0$ such that for any $(j,k)$ such that for any $j\ge 0$,
\begin{equation}\label{eq:dotC}
 \|c^{(\cdot)}_{j,\cdot}\|_{\ell^\infty(\Omega)} \le C 2^{-\alpha j}.
\end{equation}
The following result gives a sufficient condition to belong to $I^\alpha(\Omega)$.
\BThe\label{thm:in I}
Let $\alpha>0$, $f\in C^\alpha(\Omega)$ and set $M=[\alpha]+1$. If there exists $C>0$ and $\gamma>1$ such that, for any $j\ge 0$,
\begin{equation}\label{eq:hyp cn}
 \max \{
 \sup_{j\le l \le j+ \log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,
 2^{-jM} \!\!\! \sup_{j-\log_2 j \le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)}) \}
 \ge C 2^{-j\alpha} j^\gamma,
\end{equation}
then $f\in I^\alpha(\Omega)$.

Now, if $f$ belongs to $I^\alpha(\Omega)$, there exist $C>0$ and $\beta\in (0,1)$ such that for any integer $j\ge 0$,
\begin{equation}\label{eq:hyp cs}
 \max \{
 \sup_{j\le l \le j+ \log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,
 2^{-jM} j^\beta \!\!\! \sup_{j-\log_2 j \le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)}) \}
 \ge C 2^{-j\alpha}.
\end{equation}
\EThe
\BProof
To prove the first part of the theorem, let us suppose that $f\in C^\alpha_w(\R^d)$ and let $C>0$. As shown in \cite{clanic:pre}, there exists some increasing sequence of integers $(j_n)_n$ such that for any $n\in\N$ and any $j\ge j_n$,
\begin{equation}\label{eq:cn}
 \sup_{|h|\le 2^{-j}} \|\Delta_h^M f \|_{L^\infty(\Omega_h)} \le C 2^{-j_n \alpha}.
\end{equation}
 Let us show that this inequality leads to a contradiction.

For the sake of simplicity, let us suppose that $\Psi^{(1)}=\psi$ (let us recall that one of the $\Psi^{(i)}$ is $\psi$). We then have, by definition of the wavelet coefficients, for any $j\ge 0$ and any $(i,k)\in I_j$,
\begin{eqnarray*}
 c^{(i)}_{j,k} &=& 2^{jd} \int_{\R^d} f(x) \Psi^{(1)} (2^j x_1-k_1) \cdots \Psi^{(d)} (2^j x_d-k_d) \,dx \\
               &=& 2^{jd} \int_{\R^d} f(x) \Delta_{1/2}^M \Psi_M (2^j x_1-k_1) \cdots  \Psi^{(d)} (2^j x_d-k_d) \, dx \\
               &=& 2^{jd} \int_{\R^d} \Delta_{1/2^{j+1} e_1}^M f (x) \Psi_M (2^j x_1-k_1) \cdots \Psi^{(d)} (2^j x_d-k_d) \, dx,
\end{eqnarray*}
where $e_1=(1,0,\ldots,0)$. Using the assumptions on the support of $\Psi_M$ and the definition of $I_j$, one has, for any $n\in\N$, any $j\ge j_n$ and any $(i,k)\in I_j$,
\begin{eqnarray*}
 |c^{(i)}_{j,k}| &\le& 2^{jd} \int_\Omega |\Delta_{1/2^{j+1}e_1}^M f (x)| |\Psi_M (2^j x_1-k_1) \cdots \Psi^{(d)} (2^j x_d-k_d)| \, dx \\
                 &\le& C 2^{jd} 2^{-j_n\alpha} \int_{\R^d} |\Psi_M (2^j x_1-k_1) \cdots \Psi^{(d)} (2^j x_d-k_d)| \, dx \\
                 &=& C 2^{-j_n\alpha} \| \Psi_M \otimes \cdots \otimes \Psi^{(d)} \|_{L^1(\R^d)},
\end{eqnarray*}
by using Relation (\ref{eq:cn}).

For $n\in\N$, let $l_n=j_n+ \gamma [\log_2 j_n]$; for $n$ sufficiently large, one has $l_n- \log_2 l_n\ge j_n$. Therefore, the following relations hold for $n$ sufficiently large (and any $(i,k)\in I_j$),
\[
 \sup_{l_n \le j \le l_n+\log_2 l_n} |c^{(i)}_{j,k}| \le C 2^{-j_n\alpha} \le C 2^{-l_n\alpha} l_n^{\gamma'}
\]
and
\[
 \sup_{l_n-\log_2 l_n \le j \le l_n} 2^{jM} |c^{(i)}_{j,k}| \le C 2^{l_n M} 2^{-j_n \alpha} \le C 2^{l_n M} 2^{-l_n \alpha} l_n^{\gamma'},
\]
which is in contradiction with the relation (\ref{eq:hyp cn}).

To prove the second part of the theorem we will use the following result (see \cite{mey:90}): Let $f\in C^\gamma(\Omega)$; since $C^\gamma(\Omega)\subset B^0_{\infty,\infty}(\Omega) \cap \dot{C}^\gamma(\Omega)$, the wavelet characterizations of these two functional spaces lead to the existence of a constant $C>0$ that does not depend on the function such that for any $h\in\R^d$ and any $x\in\Omega_h$, one has
\begin{equation}\label{eq:meya}
 |\Delta_h^{[\gamma]+1} f(x)| \le C \sup_{j\in \N} \| c^{(\cdot)}_{j,\cdot} \|_{l^\infty(\Omega)}\;,
\end{equation}
and
\begin{equation}\label{eq:meyb}
 |\Delta_h^{[\gamma]+1} f(x)| \le C |h|^\gamma \sup_{j\in \N} \{ 2^{j\gamma} \| c^{(\cdot)}_{j,\cdot} \|_{l^\infty(\Omega)}\}.
\end{equation}
Let us assume $f\in I^\alpha(\Omega)$ and that Property (\ref{eq:hyp cs}) is not satisfied. In this case, for any $C>0$ and any $\beta\in (0,1)$, there exists an increasing sequence of integers $(j_n)_n$ such that, for any $n\in\N$,
\begin{equation}\label{eq:hyp cs contra}
 \begin{array}{cc}
 \displaystyle \max \{
 \sup_{j_n\le l \le j_n+ \log_2 j_n} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,\\
 & \displaystyle \hspace{-100pt}
 2^{-j_n M}j^\beta \!\!\! \sup_{j_n-\log_2 j_n \le l \le j_n} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)}) \}
 \end{array}
 \le C 2^{-j_n \alpha}.
\end{equation}
Let us fix $C>0$, $x\in\Omega_h$ and let $n_0\in\N$, $h\in\R^d$ be such that $|h|\le 2^{-j n_0}$. By definition of $I^\alpha(\Omega)$, we have to show that $f\in C^\alpha_w(\Omega)$. We will use the following notations:
\[
 f_{-1}= \sum_{k\in \Z^d} C_k \phi(\cdot -k), \qquad f_j= \sum_{i=1}^{2^d-1} \sum_{k\in \Z^d} c^{(i)}_{j,k} \psi(2^j \cdot -k),
\]
with $j\ge 0$. Since $f$ is uniformly H\"older, $f_j$ and $\sum_{j\ge -1} f_j$ converge uniformly on any compact set and
\[
 \Delta_h^M f= \sum_{j\ge -1} \Delta_h^M f_j.
\]

We first consider the function $g_1=\sum_{j=-1}^{j_{n_0}} f_j$. Let us fix $\gamma\in ([\alpha]+1-\beta,[\alpha]+1)$. The regularity of the wavelets and property~(\ref{eq:meyb}) imply the existence of $C>0$ not depending on $n_0$, $x$ and $h$ such that
\begin{equation}\label{eq:g1}
 |\Delta_h^M g_1(x)| \le C |h|^\gamma \sup_{l\le j_{n_0}} \left(2^{l\gamma} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)}\right).
\end{equation}
Since $f\in C^\alpha(\Omega)$, there exists a constant such that, for any $n\in\N$,
\[
 \sup_{l\le j_{n_0}- \log_2 j_{n_0}} (2^{l \gamma} \|c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})
 \le C 2^{(j_{n_0}-\log_2 j_{n_0}) (\gamma-\alpha)}
 = C' \frac{2^{j_{n_0} (\gamma-\alpha)}} {j_{n_0}^{\gamma-\alpha}}.
\]
On the other hand, we have, using relation~(\ref{eq:hyp cs contra}),
\begin{eqnarray*}
 \lefteqn{\sup_{j_{n_0}-\log_2 j_{n_0} \le l \le j_{n_0}} (2^{l \gamma} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})} \\
 &=& \sup_{j_{n_0}-\log_2 j_{n_0} \le l \le j_{n_0}} (2^{l (\gamma-M)} 2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)}) \\
 &\le& C 2^{(j_{n_0} -\log_2 j_{n_0}) (\gamma-M)} 2^{j_{n_0} (M-\alpha)}/ j_{n_0}^{\beta} \\
 &=& C' j_{n_0}^{M-\gamma} 2^{j_{n_0} (\gamma-\alpha)}/j_{n_0}^\beta \\
 &\le& C' 2^{j_{n_0} (\gamma-\alpha)} .
\end{eqnarray*}
This implies that for $n_0$ sufficiently large (since $0<M-\gamma\le \beta$),
\[
 \sup_{l\le j_{n_0}} (2^{l \gamma} \|c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})
 \le C 2^{j_{n_0} (\gamma-\alpha)},
\]
and hence, using inequality~(\ref{eq:g1}),
\begin{equation}\label{eq:g1b}
 |\Delta_h^M g_1 (x)| \le C 2^{-j_{n_0} \alpha},
\end{equation}
since $h$ has been chosen adequately.

Let us now consider $g_2= \sum_{j> j_{n_0}} f_j$. Property~(\ref{eq:meya}) applied to $g_2$ directly gives the following relation,
\begin{equation}\label{eq:g2}
 |\Delta_h^M g_2| \le C \sup_{l>j_{n_0}} (\|c^{(\cdot)}_{l,\cdot} \|_{l^\infty(\Omega)}).
\end{equation}
Once again, since $f\in C^\alpha(\Omega)$, we have
\[
 \sup_{l\ge j_{n_0} +\log_2 j_{n_0}} \| c^{(\cdot)}_{l,\cdot}\|_{\ell^\infty(\Omega)} \le C 2^{-(j_{n_0}+\log_2 j_{n_0})\alpha} = C' \frac{2^{-j_{n_0} \alpha}}{j_{n_0}^\alpha}.
\]
Now, Relation~(\ref{eq:hyp cs contra}) implies
\[
 \sup_{j_{n_0} \le l \le j_{n_0} +\log_2 j_{n_0}} \|c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} \le C 2^{-j_{n_0} \alpha}.
\]
These last inequalities lead to the following relation for $n_0$ sufficiently large,
\begin{equation}\label{eq:g2b}
 |\Delta_h^M g_2 (x)| \le C 2^{-j_{n_0} \alpha},
\end{equation}
thanks to relation~(\ref{eq:g2}).

Putting relations~(\ref{eq:g1b}) and (\ref{eq:g2b}) together, we obtain
\[
 |\Delta_h^M f (x)| = |\Delta_h^M (g_1+g_2) (x)| \le C 2^{-j_{n_0} \alpha}
\]
for $n_0$ sufficiently large, that is $f\in C^\alpha_w (\Omega)$, which is impossible, since $f\in I^\alpha(\Omega)$.
\EProof

\subsection{Characterization of the local irregularity exponent}
The preceding result leads to the following characterization of the irregularity exponent.
\BCor\label{cor:carac}
Let $\alpha>0$; if $f\in C^\alpha(\Omega)$, then the irregularity exponent of $f$ on $\Omega$ equals $\alpha$ if and only if
\[
 \lim_{j\to \infty} \frac{\displaystyle
 \log_2 \max\{ \sup_{j\le l\le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,
 2^{-jM} \sup_{j-\log_2 j\le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})
 \}}{-j} =\alpha,
\]
where $M=[\alpha]+1$.
\ECor
\BProof
Theorem~\ref{thm:in I} directly yields that if $f\in C^\alpha(\Omega)$, the irregularity exponent of $f$ on $\Omega$ equals $\alpha$ if and only if
\[
 \limsup_{j\to \infty} \frac{\displaystyle
 \log_2 \max\{ \sup_{j\le l\le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,
 2^{-jM}\!\!\! \sup_{j-\log_2 j\le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})
 \}}{-j} =\alpha.
\]
We have to prove that the $\limsup$ can be replaced by a limit. Since $f\in C^\alpha(\Omega)$, the relation~(\ref{eq:dotC}) implies that
\[
 \liminf_{j\to \infty} \frac{\displaystyle
 \log_2 \max\{ \sup_{j\le l\le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)} ,
 2^{-jM}\!\!\! \sup_{j-\log_2 j\le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(\Omega)})
 \}}{-j} =\alpha.
\]
is always larger than
\[
 \liminf_{j\to\infty} \frac{\log_2 \max \{
 \sup_{j\le l\le j+\log_2 j} 2^{-l\alpha}, 2^{-jM} \sup_{j-\log_2 j\le l \le j} 2^{l(M-\alpha)}
 \}}{-j} =\alpha,
\]
which is sufficient to conclude.
\EProof
We can now state the local version of the previous result.
\BThe\label{thm:car H}
Let $\alpha>0$; if $f\in C^\alpha(\Omega)$ and $x_0\in \R^d$, then
\[
 \uhl(x_0)= \alpha
\]
if and only if
\[
 \lim_{r\to 0} \lim_{j\to \infty} \frac{
 \begin{array}{cc}
 \displaystyle
 \log_2 \max\{ \sup_{j\le l\le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(B(x_0,r))} ,\\
 & \displaystyle \hspace{-100pt}
 2^{-jM}\!\!\! \sup_{j-\log_2 j\le l \le j} (2^{lM} \| c^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(B(x_0,r))})
 \}
 \end{array}}{-j} =\alpha,
\]
where $M=[\alpha]+1$.
\EThe

\section{A prevalent result on the $S^\nu$ spaces}
Prevalence supplies a natural definition of ``almost every'' which is translation invariant and where no specific measure plays a particular role. To prove our prevalent result, we first need to introduce the method we will use. We will also need some properties obtained in \cite{aub:07}.
\subsection{The stochastic process technique}
Our result concerning the prevalence relies on the stochastic process technique. Let us recall that a random element $X$ on a complete metric space $E$ is a measurable mapping $X$ defined on a probability space $(\Omega,\mathcal{A},P)$ with values in $E$. For a random element on $E$, one can define a probability on $E$ by the formula
\[
 P_X(A)=P\{ X\in A\}.
\]
Replacing the measure $\mu$ in Definition~\ref{def:harr-null} of a Haar-null set with $\mu=P_X$, we see that in order to prove that a set is Haar-null, it is sufficient to check that for any $f\in E$,
\[
 P_X(A+f)=0.
\]

The stochastic process that we will use here is a random wavelet series associated in a proper to $\nu$. To this end, for each $j\ge 0$, let us define as in \cite{aub:07},
\begin{equation}\label{eq:F_j}
 F_j(\alpha)= \left\{\begin{tabular}{ll}
                      $0$ & if $\alpha<\alpha_\text{min}$ ,\\
                      $2^{-jd} \sup\{j^2, 2^{j\nu(\alpha)}\}$ & if $\alpha \ge \alpha_\text{min}$ .
                     \end{tabular}\right.
\end{equation}
Since $F_j$ is non-decreasing and piecewise continuous, it is the repartition function of some probability distribution associated to a probability law $\rho_j$ supported on $[\alpha_\text{min},\infty]$, where
\[
 \alpha_\text{min}= \inf \{\alpha: \nu(\alpha)\ge 0\}.
\]
The following remark is made in \cite{aub:07}. If $\rho_j$ is the probability distribution whose repartition function $F_j$ is defined by~(\ref{eq:F_j}), then there exists some sequence of random numbers $(c_\lambda)_{\lambda\in\Lambda}$ with independent phase and moduli such that for any $j$, $\rho_j$ is the common law of $-\log_2 |c^{(i)}_{j,k}|/j$ and satisfies the two following conditions:
\begin{equation}\label{eq:soph:cond1}
 \forall \alpha\in\R,\qquad \lim_{j\to\infty} \frac{2^{jd} \rho_j((-\infty,\alpha])}{j} = \nu(\alpha),
\end{equation}
and
\begin{equation}\label{eq:soph:cond2}
 \forall \alpha\ge \alpha_\text{min},\qquad 2^{jd} \rho_j((-\infty,\alpha]) \ge j^2.
\end{equation}
Starting from these results, we will use the following random wavelet series associated to $\nu$,
\begin{equation}\label{eq:rws}
 X_\nu= \sum_{\lambda\in\Lambda} c_\lambda \psi_\lambda.
\end{equation}
It is shown in \cite{aub:06} that the metric topology $d(\cdot,\cdot)$ on $S^\nu$ makes it a Polish space, which is a very good framework for prevalence. Moreover, as proved in \cite{aub:07}, the measure $P_X$ is a Borel measure (relatively to this topology). In other words, we can use the stochastic process technique with $X_\nu$.

\subsection{Prevalent irregularity properties in $S^\nu$}
We are now ready to prove the following result.
\BThe
The following set is prevalent in $S^\nu$,
\[
 \{f: \text{$\forall x\in\T^d$, the local irregularity exponent of $f$ at $x$ is $\uhl(x)=\alpha_\text{min}$}\},
\]
where
\[
 \alpha_\text{min}= \inf \{\alpha: \nu(\alpha)\ge 0\}.
\]
\EThe
From this point of view, the ``typical elements'' of $S^\nu$ are multifractal and satisfy a weak uniform irregularity property.

From what precede, it is sufficient to show the following result.
\BPro
Let $X_\nu$ be the random wavelet series defined by~(\ref{eq:rws}). Then, for any $f\in S^\nu$, the local irregularity exponent $\uhl(x)$ of $f+X_\nu$ at $x$ is equal to $\alpha_\text{min}$ almost surely.
\EPro
\BProof
Since $S^\nu \subset C^{\alpha_\text{min}}(\T^d)$ then for any $f\in S^\nu$, $f+X_\nu \in C^{\alpha_\text{min}}(\T^d)$ almost surely. Let us now fix $m\in\N$ and define, for any $r\in \Z^d$,
\[
 T_{r,m} =  \prod_{n=1}^d ( \frac{r_n}{2^m}, \frac{r_n +1}{2^m})
\]
so that $\T^d= \cup_{r} \overline{T_{r,m}}$. We aim at showing that the equality
\[
 \uhl(T_{r,m})=\alpha_\text{min}
\]
holds almost surely for any $r,m$; in this case, Theorem~\ref{thm:car H} directly yields the required result.

For $\lambda\in \Lambda$, we will denote as usual $c_\lambda$ the wavelet coefficients associated to $X_\nu$ and $d_\lambda$ the wavelet coefficients associated to $f\in S^\nu$. Let us first remark that if for some fixed $\lambda\in \Lambda$, $\Re (c_\lambda \overline{d_\lambda})\le 0$ i.e.\ $c_\lambda$ is in the complex half-plane opposite to $d_\lambda$, then
\[
 |c_\lambda-d_\lambda| \ge |c_\lambda|
\]
Therefore, for any $\lambda\in \Lambda$,
\begin{equation}\label{eq:proba 1/2}
 P(f:|c_\lambda -d_\lambda|\ge |c_\lambda|) \ge P (f:\Re(c_\lambda \overline{d_\lambda})\le 0) \ge 1/2.
\end{equation}
If we define for any $N\in\N$ and $\lambda=(i,j,k)\in \Lambda$,
\[
 A_{N,\lambda} =\{f: (\exists k'\in k+[0,N]^d: |c^{(i)}_{j,k'}-d^{(i)}_{j,k'}|\ge |c^{(i)}_{j,k'}|)\},
\]
then, thanks to the independence of the wavelet coefficients of $X_\nu$ and inequality~(\ref{eq:proba 1/2}), we have
\[
 P(A_{N,\lambda}) \ge 1- 2^{-Nd}
\]
for any $N$ and $\lambda$.

Now, for $N\in\N$, let us set
\[
 B_{r,m,n} = \{f: \| c^{(\cdot)}_{j,\cdot} \|_{\ell^\infty(T_{r,m})} \ge 2^{-j (\alpha_\text{min} +1/n)} \}.
\]
If for any $i$, we have $\supp{\psi^{(i)}}\subset [0,M]^d$, then $\supp{\psi_\lambda}\subset T_{r,m}$ if and only if, for any $l\in\{1,\ldots,d\}$, we have $r_l 2^{j-m} \le k_l \le (r_l+1) 2^{j-m}-M$. Therefore, for any fixed $j\ge m$,
\[
 P(B_{r,m,n})=1- (1- 2^{j(\nu(\alpha_\text{min} +1/n)-d)})^{2^{d(j-m)}}
 \ge 1-\exp(-2^{-md}2^{j\nu(\alpha_\text{min}+1/n)}).
\]
Let us choose $N=2^{j-m}$; for any $m,n$ and any $j\ge m$, we have
\begin{eqnarray*}
 \lefteqn{P(f: \bigcap_r \| c^{(\cdot)}_{j,\cdot} -d^{(\cdot)}_{j,\cdot} \|_{\ell^\infty(T_{r,m})} \ge 2^{-j (\alpha_\text{min}+1/n)})} \\
 &\ge& \big(P(f: (\bigcup_{(i,k)\in I_j} A_{2^{j-m},\lambda}) \cap B_{2r,m+1,n})\big)^{2^m} \\
 &\ge& \big(1-2^{-2^{d(j-m)}} -\exp(-2^{-md} 2^{j\nu(\alpha_\text{min}+1/n)})\big)^{2^{md}}.
\end{eqnarray*}
Moreover, for any $n$,
\[
 \sum_m \sum_{j\ge m} (1-\big(1-2^{-2^{d(j-m)}} -\exp(-2^{-md} 2^{j\nu(\alpha_\text{min}+1/n)})\big)^{2^{md}}) <\infty.
\]
Therefore, the Borel-Cantelli lemma implies that for any $n$, there exists $m_0\in \N$ such that, for any $m\ge m_0$, any $r$ and any $j\ge m$, the inequality
\begin{equation}\label{eq:c-d}
 \| c^{(\cdot)}_{j,\cdot} -d^{(\cdot)}_{j,\cdot} \|_{\ell^\infty(T_{r,m})} \ge 2^{-j(\alpha_\text{min}+1/n)}
\end{equation}
holds almost surely. Using inequality~(\ref{eq:c-d}), we see that for any $n\in\N$,
\[
 \begin{array}{cc}
 \displaystyle \max\{
 \sup_{j\le l \le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(T_{r,m})}, &\\
 & \displaystyle \hspace{-100pt} 2^{-j([\alpha_\text{min}]+1)} \sup_{j-\log_2 j\le l\le j} (2^{l([\alpha_\text{min}]+1)} \|c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot}\|_{\ell^\infty(T_{r,m})}
 \}
 \end{array}
\]
is larger than $2^{-j(\alpha_\text{min}+1/n)}$ for any $r,m$ almost surely. Moreover, since $X_\nu+f\in C^{\alpha_\text{min}}(\T^d)$ almost surely, we also almost surely have that, for any $j$ and any $r,m$,
\[
 \begin{array}{cc}
 \displaystyle \max\{
 \sup_{j\le l \le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(T_{r,m})}, \\
 &\displaystyle \hspace{-100pt} 2^{-j([\alpha_\text{min}]+1)} \sup_{j-\log_2 j\le l\le j} (2^{l([\alpha_\text{min}]+1)} \|c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(T_{r,m})}
 \}
 \end{array}
\]
is lower than $2^{-j\alpha_\text{min}}$. These two bounds allows us to say that for any $n\in\N$, the quantity
\[
 \lim_{j\to\infty}\frac{
 \begin{array}{cc}
 \displaystyle \log_2 \max\{
 \sup_{j\le l \le j+\log_2 j} \| c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(T_{r,m})}, \\
  & \displaystyle \hspace{-150pt} 2^{-j([\alpha_\text{min}]+1)} \sup_{j-\log_2 j\le l\le j} (2^{l([\alpha_\text{min}]+1)} \|c^{(\cdot)}_{l,\cdot} -d^{(\cdot)}_{l,\cdot} \|_{\ell^\infty(T_{r,m})}\}
 \end{array}
  }{-j}
\]
almost surely belongs to $[\alpha_\text{min},\alpha_\text{min}+1/n]$, for any $r,m$. Since this relation is valid for any $n$, Corollary~\ref{cor:carac} allows to conclude.
\EProof

redpajama_set_name: RedPajamaArXiv