The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries

Introduction

A dictionary $\mathfrak{D}$ is simply a set of vectors (also called atoms) in $\mathcal{H}$. The number of vectors in $\mathfrak{D}$ can exceed the dimension of the Hilbert space $\mathcal{H}$, in fact, the most interesting situation is when $\left|\mathfrak{D}\right|\gg p=\dim\mathcal{H}$. In this set-up we define a resolution of the Hilbert space $\mathcal{H}$ via $\mathfrak{D}$, which is the morphism of vector spaces

In the last two decades , and in particular in recent years , resolutions of Hilbert spaces became an important tool in signal processing, in particular in the emerging theories of sparsity and compressive sensing.

The restricted isometry property

A dictionary $\mathfrak{D}$ satisfies the restricted isometry property with coefficients $\left(\delta_{1},\delta_{2},n\right)$ if for every subset $S\subset\mathfrak{D}$ such that $\left|S\right|\leq n$ we have

It is known that the RIP holds for random dictionaries. However, one would like to address the following problem :

Find deterministic construction of a dictionary $\mathfrak{D}$ with $\left|\mathfrak{D}\right|\gg p$ which satisfies RIP with coefficients in the critical regime

Incoherent dictionaries

A dictionary $\mathfrak{D}$ is called incoherent with coherence coefficient $\mu$ (also called $\mu$-coherent) if for every pair of distinct atoms $\varphi,\phi\in\mathfrak{D}$

In this article we will explore a general relation between RIP and incoherence. Our motivation comes from three examples of incoherent dictionaries which arise naturally in the setting of finite harmonic analysis:

The three examples of dictionaries we just described constitute reasonable candidates for solving Problem 1.2: They are large in the sense that $\left|\mathfrak{D}\right|\gg p,$ and empirical evidences suggest (see for the case of $\mathfrak{D}_{H})$ that they might satisfy RIP with coefficients in the critical regime (1.1). We summarize this as follows:

Do the dictionaries $\mathfrak{D}_{H},\mathfrak{D}_{O}$ and $\mathfrak{D}_{EO}$ satisfy the RIP with coefficients $\delta_{1},\delta_{2}\ll 1$ and $n=\alpha\cdot p$, for some $0<\alpha<1$?

Main results

In this article we formulate a relaxed statistical version of RIP, called statistical isometry property (SRIP for short) which holds for any incoherent dictionary $\mathfrak{D}$ which is, in addition, a disjoint union of orthonormal bases:

where $B_{x}=\left\{b_{x}^{1},..,b_{x}^{p}\right\}$ is an orthonormal basis of $\mathcal{H}$, for every $x\in\mathfrak{X}$.

Let $\mathfrak{D}$ be an incoherent dictionary of the form (3.1). Roughly, the statement is that for $S\subset\mathfrak{D}$, $\left|S\right|=n$ with $n=p^{1-\varepsilon}$, for $0<\varepsilon<1$, chosen uniformly at random, the operator norm $\left\|\mathbf{G}\left(S\right)-Id_{S}\right\|$ is small with high probability. Precisely, we have

2. The statistics of the eigenvalues

A natural thing to know is how the eigenvalues of the Gram operator $\mathbf{G}\left(S\right)$ fluctuate around $1$. In this regard, we study the spectral statistics of the normalized error term

Let $\rho_{\mathbf{E}\left(S\right)}=n^{-1}\sum_{i=1}^{n}\delta_{\lambda_{i}}$ denote the spectral distribution of $\mathbf{E}\left(S\right)$ where $\lambda_{i}$, $i=1,..,n$, are the real eigenvalues of the Hermitian operator $\mathbf{E}\left(S\right)$. The following theorem asserts that $\rho_{\mathbf{E}}$ converges in probability as $p\rightarrow\infty$ to the Wigner semicircle distribution $\rho_{SC}\left(x\right)=\left(2\pi\right)^{-1}\sqrt{4-x^{2}}\cdot\mathbf{1}_{\left[2,-2\right]}\left(x\right)$ where $\mathbf{1}_{\left[2,-2\right]}$ is the characteristic function of the interval $\left[-2,2\right]$.

A limit of the form (3.3) is familiar in random matrix theory as the asymptotic of the spectral distribution of Wigner matrices. Interestingly, the same asymptotic distribution appears in our situation, albeit, the probability spaces are of a different nature (our probability spaces are, in particular, much smaller).

In particular, Theorems 3.1, 3.2 can be applied to the three examples $\mathfrak{D}_{H}$, $\mathfrak{D}_{O}$ and $\mathfrak{D}_{EO}$, which are all of the appropriate form (3.1). Finally, our result gives new information on a remark of Applebaum-Howard-Searle-Calderbank concerning RIP of the Heisenberg dictionary.

For practical applications, it might be important to compute explicitly the constants $C\left(k\right)$ which appears in (3.2). This constant depends on the incoherence coefficient $\mu$, therefore, for a fixed $p$, having $\mu$ as small as possible is preferable.

It is a pleasure to thank our teacher J. Bernstein for his continuos support. We are grateful to N. Sochen for many stimulating discussions. We thank F. Bruckstein, R. Calderbank, M. Elad, Y. Eldar, R. Kimmel, and A. Sahai for sharing with us some of their thoughts about signal processing. We are grateful to R. Howe, A. Man, M. Revzen and Y. Zak for explaining us the notion of mutually unbiased bases.

References