Convex recovery of a structured signal from independent random linear measurements

Motivation

Signal reconstruction from random measurements is a central preoccupation in contemporary signal processing. In this problem, we acquire linear measurements of an unknown, structured signal through a random sampling process. Given these random measurements, a standard method for recovering the unknown signal is to solve a convex optimization problem that enforces our prior knowledge about the structure. The basic question is how many measurements suffice to resolve a particular type of structure.

Recent research has led to a comprehensive answer when the measurement operator follows the standard Gaussian distribution [MPTJ07, RV08, Sto09, OH10, CRPW12, ALMT14, FM14, OH13, OTH13, TOH14]. The literature also contains satisfying answers for subgaussian measurements [MPTJ07] and subexponential measurements [Men10]. Other types of measurement systems are quite common, but we are not aware of a simple approach that allows us to analyze general measurements in a unified way.

This chapter describes an approach that addresses a wide class of convex signal reconstruction problems involving random sampling. To understand these questions, the core challenge is to produce a lower bound on a nonnegative empirical process. For this purpose, we rely on a powerful framework, called the Small Ball Method, that was developed by Shahar Mendelson and coauthors in a sequence of papers, including [KM13, Men13, Men14a, LM14, Men14b].

To complete the estimates required by Mendelson’s Small Ball Method, we propose a technique based on conic duality. One advantage of this approach is that we can exploit the same insights and calculations that have served so well in the Gaussian setting. We refer to this little argument as the bowling scheme in honor of David Gross’s golfing scheme [Gro11]. We anticipate that it will offer researchers an effective way to analyze many signal recovery problems with random measurements.

The first half of the chapter summarizes the established analysis of convex signal reconstruction with a Gaussian sampling model. In Section 2, we introduce a convex optimization framework for solving structured signal recovery problems with linear measurements, and we present a geometric formulation of the optimality conditions. Section 3 specializes to the case where the measurements come from a Gaussian model, and we explain how classical results for Gaussian processes lead to a sharp bound for the number of Gaussian measurements that suffice. These results are framed in terms of a geometric parameter, the conic Gaussian width, associated with the convex optimization problem. Section 4 explains how to use duality to obtain a numerically sharp bound for the conic Gaussian width, and it develops two important examples in detail.

In the second half of the chapter, we consider more general sampling models. Section 5 introduces Mendelson’s Small Ball Method and the technical arguments that support it. As a first application, in Section 6, we use this strategy to analyze signal reconstruction from subgaussian measurements. Section 7 presents the bowling scheme, which merges the conic duality estimates with Mendelson’s Small Ball Method. This technique allows us to study more general types of random measurements. Finally, in Section 8, we demonstrate the vigor of these ideas by applying them to the phase retrieval problem.

Signal reconstruction from linear measurements

2. Reconstruction via convex optimization

where $\left\|{\cdot}\right\|$ denotes the Euclidean norm and $\eta$ is a specified bound on the norm of the error $\bm{e}$. In words, the optimization problem (2.2) searches for the most structured signal $\bm{x}$ that is consistent with the observed data $\bm{y}$. In practice, it is common to consider the Lagrangian formulation of (2.2) or to consider a problem where the objective and constraint are interchanged. We can often solve (2.2) and its variants efficiently using standard algorithms.

where $f^{\circ}$ denotes the polar of the gauge [Roc70, Chap. 15] and t denotes transposition. This reconstruction method submits to an analysis similar with the approach in this note. For example, see [CLR14, Thm. 1].

3. Examples

Before we continue, let us mention a few structures that arise in applications and the complexity measures that are typically associated with these structures.

Sparsity has become a dominant modeling tool in statistics, machine learning, and signal processing.

In recent years, this approach to fitting low-rank matrices has become common.

It is possible to consider many other types of structure. For instance, see [CRPW12, FM14].

4. A deterministic error bound for convex recovery

The descent cone of a convex function is always a convex cone, but it may not be closed.

We are interested in the behavior of the measurement matrix $\bm{\Phi}$ when it is restricted to a descent cone.

With these definitions at hand, we reach the following basic result.

This statement is adapted from [CRPW12]. For completeness, we include the short proof.

It is natural to write the decision variable $\bm{x}$ in the convex program (2.2) relative to the true unknown: $\bm{u}:=\bm{x}-\bm{x}^{\natural}$. Using the expression (2.1) for the measurement vector $\bm{y}$, we obtain the equivalent problem

Owing to the bound $\left\|{\bm{e}}\right\|\leq\eta$, the point $\bm{u}=\bm{0}$ is feasible for (2.6). Therefore, each optimal point $\widehat{\bm{u}}$ verifies $f(\bm{x}^{\natural}+\widehat{\bm{u}})\leq f(\bm{x}^{\natural})$. In summary, any optimal point of (2.6) satisfies two conditions:

As a consequence, we simply need to determine how far we can travel in a descent direction before we violate the bound constraint. See Figure 2.1 for an illustration of the geometry.

To complete the argument, assume that $\bm{u}$ is a nonzero point in $\mathcal{D}(f,\bm{x}^{\natural})$ that is feasible for (2.6). Then

The first inequality follows from Definition 2.5 of the conic singular value. The second relation is the triangle inequality. The last bound holds because $\bm{u}$ satisfies the constraint in (2.6), and we have assumed that $\left\|{\bm{e}}\right\|\leq\eta$. Finally, rearrange the display, and rewrite $\bm{u}$ in terms of the original decision variable $\bm{x}$. ∎

Although Proposition 2.6 is elegant, it can be difficult to apply because we must calculate the minimum conic singular value of a matrix $\bm{\Phi}$ with respect to a descent cone. This challenge becomes less severe, however, when the matrix $\bm{\Phi}$ is drawn at random.

A universal error bound for Gaussian measurements

We will study the prospects for convex recovery when the sampling matrix $\bm{\Phi}$ is chosen at random. This modeling assumption arises in signal processing applications where the matrix describes a data-acquisition system that can extract random measurements. This kind of model also appears in statistics and machine learning when each row of the matrix tabulates measured variables for an individual subject in an experiment.

In this section, we treat one of the simplest mathematical models for the $m\times d$ random measurement matrix $\bm{\Phi}$. We assume that each of the $m$ rows of $\bm{\Phi}$ is drawn independently from the standard Gaussian distribution $\textsc{normal}(\bm{0},\mathbf{I}_{d})$, where the covariance $\mathbf{I}_{d}$ is the $d$-dimensional identity matrix. For this special case, we can obtain a sharp estimate for the minimum conic singular value $\lambda_{\min}(\bm{\Phi};K)$ for any convex cone $K$.

2. The conic Gaussian width

The analysis of Gaussian sampling depends on a geometric summary parameter for cones.

The Gaussian width plays a central role in asymptotic convex geometry [MS86, Pis89, LT91]. Most of the classical techniques for bounding widths are only accurate up to constant factors (or worse). In contrast, ideas from the contemporary signal processing literature frequently allow us to produce numerically sharp estimates for the Gaussian width of a cone. These techniques were developed in the papers [Sto09, OH10, CRPW12, ALMT14, FM14]. We will outline one of the methods in Section 4.

The conic Gaussian width $w(K)$ is a convenient functional because it arises from the probabilistic tools that we use. The theory of conic integral geometry, however, delivers a better summary parameter [ALMT14]. The statistical dimension $\delta(K)$ of a convex cone $K$ can be defined as

As a consequence, we can interpret $w^{2}(K)$ as a rough measure of the “dimension” of a cone.

3. Conic singular values and conic Gaussian widths

As it turns out, the conic Gaussian width $w(K)$ controls the minimum conic singular value $\lambda_{\min}(\bm{\Phi};K)$ when $\bm{\Phi}$ follows the standard normal distribution.

In essence, this result dates to the work of Gordon [Gor85, Gor88]. We have drawn the proof from the survey [DS01, Sec. 3.2] of Davidson & Szarek; see also [MPTJ07, RV08, Sto09, CRPW12]. Note that the argument relies on special results for Gaussian processes that do not extend to other distributions.

We can express the minimum conic singular value as

It is a consequence of Gordon’s comparison inequality [Gor85, Thm. 1.4] that

To complete the argument, note that the map

is 1-Lipschitz with respect to the Frobenius norm. The usual Gaussian concentration inequality [BLM13, Sec. 5.4] implies that

Introduce the lower bound (3.1) for the expectation of the minimum conic singular value into (3.2) to reach the advertised result. ∎

It is a remarkable fact that the bound in Proposition 3.3 is essentially sharp. For any cone $K$, we can reinterpret the statement as saying that

(The letter $C$ always denotes a positive absolute constant, but its value may change from place to place.) Conversely, for a convex cone $K$, it holds that

The result (3.3) follows from research of Amelunxen et al. [ALMT14, Thm. I and Prop. 10.2]. This claim can also be derived by supplementing the proof of Proposition 3.3 with a short polarity argument. It is productive to interpret the pair of estimates in this remark as a phase transition for convex signal recovery; see [ALMT14] for more information.

4. An error bound for Gaussian measurements

Combining Proposition 2.6 and Proposition 3.3, we obtain a general error bound for convex recovery from Gaussian measurements.

The operation $[a]_{+}:=\max\{a,0\}$ returns the positive part of a number.

The overall argument that leads to this result was proposed by Rudelson & Vershynin [RV08, Sec. 4]; the statement here is adapted from [CRPW12].

Corollary 3.5 provides for stable recovery of the unknown $\bm{x}^{\natural}$ when the number $m$ of measurements satisfies

In view of Remark 3.4, Corollary 3.5 provides a refined estimate for the amount of information that suffices to identify a structured vector from Gaussian measurements via convex optimization.

It is possible to improve the error bound in Corollary 3.5 if we instate a Gaussian model for the error vector $\bm{e}$. See the papers [OH13, OTH13, TOH14] for an analysis of this case.

Controlling the width of a descent cone via polarity

As soon as we know the conic Gaussian width of the descent cone, Corollary 6.4 yields error bounds for convex recovery of a structured signal from Gaussian measurements. To make use of this result, we need technology for calculating these widths. This section describes a mechanism, based on polarity, that leads to extremely accurate estimates. We can trace this method to the papers [Sto09, OH10], where it is couched in the language of duality for cone programs. The subsequent papers [CRPW12, ALMT14] rephrase these ideas in a more geometric fashion. It can be shown that the approach in this section gives sharp results for many natural examples; see [ALMT14, Thm. 4.3] or [FM14, Prop. 1]. Although polar bounds for widths are classic in asymptotic convex geometry [MS86, Pis89, LT91], the refined arguments here are just a few years old.

We begin with some classical facts about conic geometry.

It is easy to verify that $K\subset(K^{\circ})^{\circ}$.

With these definitions, we reach the following weak duality result.

The argument is based on a simple duality trick. First, write

By definition of polarity, the inner supremum takes the value $+\infty$ unless $\bm{u}\in(K^{\circ})^{\circ}$. We determine that

The last inequality holds because $K\subset(K^{\circ})^{\circ}$. ∎

If $K$ is a convex cone and we replace the sphere with a ball, then we have strong duality instead:

The proof uses Sion’s minimax theorem [Sio58] and the bipolar theorem [Roc70, Thm. 14.1].

2. The conic Gaussian width of a descent cone

We can use Proposition 4.2 to obtain an effective bound for the width of a descent cone. This approach is based on a classical polarity correspondence [Roc70, Thm. 23.7].

Assume that the subdifferential $\partial f(\bm{x})$ is nonempty and does not contain the origin. Then

Combining Proposition 4.2 and Fact 4.4, we reach a bound for the conic Gaussian width of a descent cone.

Several specific instances of Proposition 4.5 appear in [CRPW12, App. C], while the general statement here is adapted from [ALMT14, Sec. 4.1]. Sections 4.3 and 4.4 exhibit how Proposition 4.5 works.

The expression (4.1) for the polar of a descent cone implies that

Indeed, the distance to a set is the same as the distance to its closure, and the distance to a union is the infimal distance to one of its members. Square the latter display, and apply Jensen’s inequality to complete the argument. ∎

3. Example: Sparse vectors

How many measurements are sufficient to ensure that this approach succeeds? We will demonstrate that

Therefore, Corollary 3.5 implies that $m\gtrsim 2s\log(d/s)$ measurements are enough for us to recover $\bm{x}^{\natural}$ approximately. When $s\ll d$, the first term in (4.2) is numerically sharp because of [FM14, Prop. 1].

Let us establish the width bound (4.2). This analysis is adapted from [CRPW12, App. C] and [ALMT14, App. D.2]; see also [FM14, App. B]. The result [ALMT14, Prop. 4.5] contains a more complicated formula for the width that is sharp for all choices of the sparsity $s$.

The distribution of a standard Gaussian random variable is invariant under signed permutation, so the conic Gaussian width has the same invariance. Therefore,

We will use this type of transformation several times without detailed justification.

As a consequence of the argument in the last paragraph, we may assume that $\bm{x}^{\natural}$ takes the form

As usual, $[a]_{+}:=\max\{a,0\}$. For $1\leq j\leq s$, a direct calculation gives

For $s<j\leq d$, we apply a familiar tail bound for the standard normal variable to obtain

Combine (4.3), (4.4), (4.5), and (4.6) to obtain

Choose $\tau^{2}=2\log(d/s)$ and simplify to reach (4.2).

4. Example: Low-rank matrices

How many measurements are enough to guarantee that this approach works? We will prove that

As a consequence, Corollary 3.5 implies that $m\gtrsim 3r\cdot(d_{1}+d_{2}-r)$ measurements allow us to identify $\bm{X}^{\natural}$ approximately.

Let us establish the width bound (4.7). This analysis is adapted from [CRPW12, App. C] and [ALMT14, App. D.3]; see also [FM14, App. E]. The result [ALMT14, Prop. 4.6] contains a more complicated formula for the width that is sharp whenever the rank $r$ is proportional to the dimension $\min\{d_{1},d_{2}\}$.

The Schatten 1-norm is unitarily invariant, so we may also select a coordinate system where

Let $\bm{G}$ be a $d_{1}\times d_{2}$ matrix with independent standard normal entries, partitioned as

Define a random parameter $\tau=\left\|{\bm{G}_{22}}\right\|$, where $\left\|{\cdot}\right\|$ denotes the spectral norm. Proposition 4.5 ensures that

Our selection of $\tau$ ensures that the last term on the right-hand side of (4.9) vanishes. By direct calculation,

To bound the first term on right-hand side of (4.9), observe that

The spectral norm is 1-Lipschitz, so the Gaussian Poincaré inequality [BLM13, Thm. 3.20] implies

Finally, we incorporate (4.9), (4.11), (4.10), and (4.12) into the width bound (4.8) to reach

Simplify this expression to obtain the result (4.7).

Mendelson’s Small Ball Method

In Sections 2–4, we analyzed a convex programming method for recovering structured signals from standard Gaussian measurements. The main result, Corollary 3.5, is appealing because it applies to any convex complexity measure $f$. Proposition 4.5 allows us to instantiate this result because it provides a mechanism for controlling the Gaussian width of a descent cone. On the other hand, this approach only works when the sampling matrix $\bm{\Phi}$ follows the standard Gaussian distribution.

For other sampling models, researchers use a variety of ad hoc techniques to study the recovery problem. It is common to see a separate and intricate argument for each new complexity measure $f$ and each new distribution for $\bm{\Phi}$. It is natural to wonder whether there is a single approach that can address a broad class of complexity measures and sampling matrices.

The primary goal of this chapter is to analyze convex signal reconstruction with more general random measurements. Our argument is based on Mendelson’s Small Ball Method, a powerful strategy for establishing a lower bound on a nonnegative empirical process [KM13, Men13, Men14a, LM14, Men14b]. This section contains an overview of Mendelson’s Small Ball Method. Section 6 uses this technique to study subgaussian measurement models. In Section 7, we extend these ideas to a larger class of sampling distributions. In Section 8, we conclude with an application to the problem of phase retrieval.

When the sampling matrix is Gaussian, we can use Gordon’s theorem [Gor85, Thm. 1.4] to obtain a lower bound for the expression (5.2), as in Proposition 3.3. The challenge is to find an alternative method for producing a lower bound in a more general setting.

2. A lower bound for nonnegative empirical processes

The main technical component in Mendelson’s Small Ball Method is a remarkable estimate that was developed in the paper [Men14a]. This result delivers an effective lower bound for a nonnegative empirical process.

Let $\varepsilon_{1},\dots,\varepsilon_{m}$ be independent Rademacher random variables,A Rademacher random variable takes the two values $\pm 1$ with equal probability. independent from everything else, and define the mean empirical width of the set:

The proof appears below in Section 5.5. In the sequel, we usually lighten our notation for $Q_{\xi}$ and $W_{m}$ by suppressing the dependence on $\bm{\varphi}$.

Before we continue, it may be helpful to remark on this result. The marginal tail function $Q_{\xi}(E)$ reflects the probability that the random variable $\left|{\left\langle{\smash{\bm{\varphi}}},\ {\bm{u}}\right\rangle}\right|$ is close to zero for any fixed vector $\bm{u}\in E$. When $Q_{\xi}(E)$ is bounded away from zero for some $\xi$, the nonnegative empirical process is likely to be large. Koltchinskii & Mendelson [KM13] point out that the marginal tail function reflects the absolute continuity of the distribution of $\bm{\varphi}$, so $Q_{\xi}$ may be quite small when $\bm{\varphi}$ is “spiky.”

3. Mendelson’s Small Ball Method

Proposition 5.1 shows that we can obtain a lower bound for (5.2) by performing two simpler estimates. To achieve this goal, Mendelson has developed a general strategy, which consists of three steps:

This presentation is distilled from the corpus [KM13, Men13, Men14a, LM14, Men14b]. A more sophisticated variant of this method appears in [Men14a, Thm. 5.3]. Later in this chapter, we will encounter several concrete applications of this strategy.

4. Expected Scope

Mendelson’s Small Ball Method provides lower bounds for (5.2) in many situations, but it does not offer a universal prescription. Let us try to delineate the circumstances where this approach is likely to be useful for signal recovery problems.

Mendelson’s Small Ball Method assumes that the sampling matrix $\bm{\Phi}$ has independent, identically distributed rows. Although this model describes many of the sampling strategies in the literature, there are some examples, such as random filtering [TWD+06], that do not conform to this assumption.

A major advantage of Mendelson’s Small Ball Method is that it applies to sampling distributions with heavy tails. On the other hand, the random vector $\bm{\varphi}$ cannot be too “spiky,” or else it may not be possible to produce a good lower bound for the marginal tail function $Q_{2\xi}(E)$. This requirement indicates that the approach may require significant improvements before it applies to problems like matrix completion.

There are a number of possible extensions of Mendelson’s Small Ball Method that could expand its bailiwick. For example, it is easy to extend Proposition 5.1 to address the case where the random vector $\bm{\varphi}$ is complex-valued. A more difficult, but very useful, modification would allow us to block the measurements into groups. This revision could reduce the difficulties associated with spiky distributions, but it seems to demand some additional ideas.

5. Proof of Proposition 5.1

Let us establish the Mendelson bound for a nonnegative empirical process. First, we introduce a directional version of the marginal tail function:

Lyapunov’s inequality and Markov’s inequality give the numerical bounds

To control the supremum in probability, we can invoke the bounded difference inequality [BLM13, Sec. 6.1]. Observe that each summand is independent and bounded in magnitude by one. Therefore,

Next, we simplify the expected supremum. Introduce a soft indicator function:

In the first line, we write the marginal tail function as an expectation, and then we bound the two indicators using the soft indicator function. The next inequality is the Giné–Zinn symmetrization [vdVW96, Lem. 2.3.1]. The last line follows from the Rademacher comparison principle [LT91, Eqn. (4.20)] because $\xi\psi_{\xi}$ is a contraction.

Combine the inequalities (5.4), (5.5), and (5.5) to reach

Define $\bm{h}:=m^{-1/2}\sum_{i=1}^{m}\varepsilon_{i}\bm{\varphi}_{i}$, and clear the factor $\sqrt{m}$ to conclude that

A universal error bound for subgaussian measurements

In this section, we invoke Mendelson’s Small Ball Method to study convex signal recovery from independent subgaussian measurements. This class of examples provides a wide generalization of standard Gaussian measurements. We will establish a variant of the Gaussian recovery result, Corollary 3.5, in this setting.

[Nondegeneracy] There is a positive constant $\alpha$ for which

[Subgaussian marginals] There is a positive constant $\sigma$ for which

[Low eccentricity] The eccentricity $\rho:=\sigma/\alpha$ of the distribution should be small.

Finally, we construct a random $m\times d$ sampling matrix $\bm{\Phi}$ whose rows are independent copies of $\bm{\varphi}^{\mathsf{t}}$, as in the expression (5.1).

A few examples of subgaussian distributions may be helpful.

Let $X$ be a symmetric random variable whose magnitude is bounded by $\sigma$. Suppose that each entry of $\bm{\varphi}$ is an independent copy of $X$.

2. The minimum conic singular value of a subgaussian matrix

The main result of this section gives a lower bound for the minimum conic singular value of a matrix $\bm{\Phi}$ that satisfies the conditions in Section 6.1.

Observe that, when the eccentricity $\rho$ has constant order, the bound in Theorem 6.3 matches the result for Gaussian matrices in Proposition 3.3. A similar result appears in the paper [MPTJ07], so we do not claim any novelty. We establish Theorem 6.3 below in Section 6.2.

3. An error bound for subgaussian measurements

Combining Proposition 2.6 and Theorem 6.3, we reach an immediate consequence for signal recovery from subgaussian measurements.

The quantities $c$ and $C$ are positive absolute constants. The operation $[a]_{+}:=\max\{a,0\}$ returns the positive part of a number.

Corollary 6.4 provides for stable recovery of $\bm{x}^{\natural}$ as soon as the number $m$ of subgaussian measurements satisfies

How accurate is this result? Note that standard Gaussian measurements satisfy the assumptions of the corollary with $\rho$ constant, and we need at least w^{2}\big{(}\mathcal{D}(f,\bm{x}^{\natural})\big{)} standard normal measurements to recover the structured signal $\bm{x}^{\natural}$ with the complexity measure $f$. Therefore, the bound is correct up to the constant factor $C^{\prime}$ and the precise dependence on the eccentricity $\rho$.

4. Proof of Theorem 6.3: Setup and Step 1

To establish Theorem 6.3, we rely on Mendelson’s Small Ball Method. The argument also depends on some deep ideas from the theory of generic chaining [Tal05], but we only use these results in a naïve way.

This result holds for all $\xi>0$ and $t>0$. To establish Theorem 6.3, we must develop a constant lower bound for the marginal tail function $Q_{2\xi}(E)$, and we also need to compare the mean empirical width $W_{m}(E)$ with the conic Gaussian width $w(K)$.

5. Step 2: The marginal tail function

We begin with the lower bound for the marginal tail function $Q_{2\xi}$. This result is an easy consequence of the second moment method, also known as the Paley–Zygmund inequality. Let $\bm{u}$ be any vector in $E$. One version of the second moment method states that

To control the denominator on the right-hand side of (6.2), we use the subgaussian marginal condition to estimate that

for any $\xi$ that satisfies $2\xi<\alpha$.

6. Step 3: The mean empirical width

Next, we demonstrate that the empirical width $W_{m}(E)$ is controlled by the conic Gaussian width $w(K)$. This argument requires sophisticated results from the theory of generic chaining [Tal05]. First, observe that the vector $\bm{h}=m^{-1/2}\sum\nolimits_{i=1}^{m}\varepsilon_{i}\bm{\varphi}_{i}$ inherits subgaussian marginals from the centered subgaussian distribution $\bm{\varphi}$. Indeed,

See [Ver12, Sec. 5.2.3] for an introduction to subgaussian random variables. In particular, we have the bound

Under the latter condition, the generic chaining theorem [Tal05, Thm. 1.2.6] asserts that

where $\gamma_{2}$ is a geometric functional. The precise definition of $\gamma_{2}$ is not important for our purposes because the majorizing measure theorem [Tal05, Thm. 2.1.1] states that

where $\bm{g}\sim\textsc{normal}(\bm{0},\mathbf{I}_{d})$. It follows that

We have recalled that $E=K\cap\mathsf{S}^{d-1}$ to identify the conic Gaussian width $w(K)$.

7. Combining the bounds

Combine the bounds (6.1), (6.3), and (6.4) to discover that

provided that $2\xi<\alpha$. Select $\xi=\alpha/6$ to see that

Using the eccentricity $\rho=\sigma/\alpha$, we simplify the expression (6.5) to reach a bound for the minimum conic singular value of a subgaussian random matrix $\bm{\Phi}$ that satisfies the conditions set out in Section 6.1. This completes the proof of Theorem 6.3.

The bowling scheme

As we have seen in Theorem 6.3, subgaussian sampling models exhibit behavior similar with the standard Gaussian measurement model. Yet there are many interesting problems where the random sampling matrix does not conform to the subgaussian assumption. In this section, we explain how to adapt Mendelson’s Small Ball Method to a range of other sampling ensembles. The key idea is to use the conic duality arguments from Section 4 to complete the estimate for the mean empirical width.

Let us state a simple duality result for the mean empirical width of a descent cone. This bound is based on the same principles as Proposition 4.5.

The mean empirical width $W_{m}$ is defined in (5.3). The random vectors $\bm{\varphi}_{1},\dots,\bm{\varphi}_{m}$ are independent copies of $\bm{\varphi}$, and $\varepsilon_{1},\dots,\varepsilon_{m}$ are independent Rademacher random variables.

The argument is identical with the proof of Proposition 4.5 once we replace the Gaussian vector $\bm{g}$ with the random vector $\bm{h}$. ∎

2. The bowling scheme

We are now prepared to describe a general approach for convex signal recovery from independent random measurements.

We want to produce a bound of the form (7.1) when the rows of the measurement matrix $\bm{\Phi}$ are independent copies of a random vector $\bm{\varphi}$. This problem falls within the scope of Mendelson’s Small Ball Method. Introduce the index set $E:=\mathcal{D}(f,\bm{x}^{\natural})\cap\mathsf{S}^{d-1}$. In light of (5.2),

We follow Mendelson’s general strategy to control the minimum conic singular value, but we propose a specific technique for bounding the mean empirical width that exploits the structure of the index set $E$.

In other words, Step (3) of Mendelson’s framework has been specialized to Step (3′).

We refer to this instance of Mendelson’s Small Ball Method as the bowling scheme. The name is chosen as a salute to David Gross’s golfing scheme. Whereas the golfing scheme is based on dual optimality conditions for the signal recovery problem (2.2), the bowling scheme is based on the primal optimality condition through Proposition 2.6. In the bowling scheme, duality enters only when we are ready to estimate the mean empirical width.

In our experience, this idea has been successful whenever we understand how to bound the conic Gaussian width of the descent cone. The main distinction is that the random vector $\bm{\varphi}$ may not share the rotational invariance of the standard Gaussian distribution.

Example: Phase retrieval

To demonstrate how the bowling scheme works, we consider the question of phase retrieval. In this problem, we collect linear samples of an unknown signal, but we are only able to observe their magnitudes. To reconstruct the original signal, we must resolve the uncertainty about the phases (or signs) of the measurements. There is a natural convex program that can achieve this goal, and the bowling scheme offers an easy way to analyze the number of measurements that are required.

Although the samples do not initially appear linear, we can apply a lifting method proposed by Balan et al. [BBCE09]. Observe that

In view of this expression, it is appropriate to introduce the rank-one positive-semidefinite matrices

Then we can express the samples $y_{i}$ as linear functions of the matrix $\bm{X}^{\natural}$:

The expression (8.3) coincides with the measurement model (2.1) we have been considering.

We can use convex optimization to reconstruct the unknown matrix $\bm{X}^{\natural}$. It is natural to minimize the Schatten 1-norm to promote low rank, but we also want to enforce the fact that $\bm{X}^{\natural}$ is positive semidefinite [Faz02]. To that end, we consider the convex program

This formulation involves the lifted variables (8.2). We say that the optimization problem (8.4) recovers $\bm{x}^{\natural}$ if the matrix $\bm{X}^{\natural}$ is the unique minimizer. Indeed, in this case, we can reconstruct the original signal by factorizing the solution to the optimization problem.

The formulation (8.4) was developed by a working group at the meeting “Frames for the finite world: Sampling, coding and quantization,” which took place at the American Institute of Mathematics in Palo Alto in August 2008. Most of the recent literature attributes this idea incorrectly.

2. Phase retrieval from Gaussian measurements

Then each sampling matrix $\bm{\Psi}_{i}=\bm{\psi}_{i}\bm{\psi}_{i}^{\mathsf{t}}$ follows a Wishart distribution. These random matrices do not have subgaussian marginals, so we cannot apply Corollary 6.4 to study the performance of the optimization problem (8.4). Nevertheless, we can make short work of the analysis by using the bowling scheme.

There are a number of obvious improvements to Theorem 8.2 that follow with a little more effort. For example, it is clear that the convex phase retrieval method is stable. The exceedingly high success probability also allows us to establish uniform results for all $d$-dimensional vectors by means of net arguments and union bounds. Furthermore, the Gaussian assumption is inessential; it is possible to establish similar theorems for other sampling distributions. We leave these refinements for the avid reader.

3. Proof of Theorem 8.2: Setup

With this notation, we can write (8.4) in the form

The formulation (8.5) matches our core problem (2.2) with the error vector $\bm{e}=\bm{0}$ and error tolerance $\eta=0$.

Proposition 2.6 demonstrates that $\bm{X}^{\natural}$ is the unique solution of (8.5) whenever

We must determine how many measurements $m$ suffice for this event to hold with high probability.

4. Step 1: The nonnegative empirical process bound

Here, $\{\varepsilon_{i}\}$ is an independent family of Rademacher random variables, independent from everything else.

5. Step 2: The marginal tail function

We can use the Paley–Zygmund inequality to show that

We have implicitly chosen $\xi=\tfrac{1}{2}$, and $c_{0}$ is a positive absolute constant.

To perform this estimate, we apply the Paley–Zygmund inequality in the form

The easiest way to treat the expectation in the denominator is to invoke Gaussian hypercontractivity [LT91, Sec. 3.2]. Indeed,

because $\left\langle{\bm{\Psi}_{1}},\ {\bm{U}}\right\rangle$ is a second-order polynomial in the entries of $\bm{\psi}_{1}$. Combine the last two displays to obtain

We can bound the remaining expectation by means of an explicit calculation. Assuming that $\bm{U}\in E$,

We have used the fact that $\bm{U}$ is a symmetric matrix with unit Frobenius norm. In conclusion,

6. Step 3′: The mean empirical width of the descent cone

We can apply Proposition 7.1 to demonstrate that the mean empirical width satisfies

The numbers $C_{1}$ and $C_{2}$ are positive, absolute constants.

The bound holds trivially when $\bm{X}^{\natural}=\bm{0}$, so we may assume that the unknown matrix is nonzero. Select a coordinate system where

Recall that the matrix $\bm{H}=m^{-1/2}\sum_{i=1}^{m}\varepsilon_{i}\bm{\Psi}_{i}$, where $\bm{\Psi}_{i}=\bm{\psi}_{i}\bm{\psi}_{i}^{\mathsf{t}}$ and $\bm{\psi}_{i}\sim\textsc{normal}(\bm{0},\mathbf{I}_{d})$. Partition $\bm{H}$ conformally with $\bm{X}^{\natural}$:

Define the random parameter $\tau=\lambda_{\max}(\bm{H}_{22})$, where $\lambda_{\max}$ denotes the maximum eigenvalue of a symmetric matrix. Proposition 7.1 delivers the width bound

Using standard calculus rules for subdifferentials [Roc70, Chap. 23], we determine that

By construction, the third term on the right-hand side of (8.10) is zero. By direct calculation, the second term on the right-hand side of (8.10) satisfies

Finally, we turn to the first term on the right-hand side of (8.10). Relatively crude bounds suffice here. By interlacing of eigenvalues,

Standard net arguments, such as those in [Ver12, Sec. 5.4.1], demonstrate that

Introducing (8.10), (8.11), and (8.12) into (8.9), we arrive at the required bound (8.8).

The only challenging part of the calculation is the bound on $\lambda_{\max}(\bm{H})$. For more general sampling distributions, we can easily obtain the required estimate from the matrix moment inequality [CGT12, Thm. A.1].

7. Combining the bounds

Assume that $m\geq C_{2}d$. Combine the estimates (8.6), (8.7), and (8.8) to reach

Acknowledgments

JAT gratefully acknowledges support from ONR award N00014-11-1002, AFOSR award FA9550-09-1-0643, and a Sloan Research Fellowship. Thanks are also due to the Moore Foundation.

References