Simultaneously Structured Models with Application to Sparse and Low-rank Matrices

Introduction

Recovery of a structured model (signal) given a small number of linear observations has been the focus of many studies recently. Examples include recovering sparse or group-sparse vectors (which gave rise to the area of compressed sensing) , low-rank matrices , and the sum of sparse and low-rank matrices , among others. More generally, the recovery of a signal that can be expressed as the sum of a few atoms out of an appropriate atomic set has been studied in . Canonical questions in this area include: How many generic linear measurements are enough to recover the model by any means? How many measurements are enough for a tractable approach, e.g., solving a convex optimization problem? In the statistics literature, these questions are posed in terms of sample complexity and error rates for estimators minimizing the sum of a quadratic loss function and a regularizer that reflects the desired structure .

There are many applications where the model of interest is known to have several structures at the same time (Section 1.2). We then seek a signal that lies in the intersection of several sets defining the individual structures (in a sense that we will make precise later). The most common convex regularizer (penalty) used to promote all structures together is a linear combination of well-known regularizers for each structure. However, there is currently no general analysis and understanding of how well such regularization performs in terms of the number of observations required for successful recovery of the desired model. This paper addresses this ubiquitous yet unexplored problem; i.e., the recovery of simultaneously structured models.

We introduce a framework to express general simultaneous structures, and as our main result, we prove that the same phenomenon happens for a general set of structures. We are able to analyze a wide range of measurement ensembles, including subsampled standard basis (i.e. matrix completion), Gaussian and subgaussian measurements, and quadratic measurements. Table 2 summarizes known results on recovery of some common structured models, along with a result of this paper specialized to the problem of low-rank and sparse matrix recovery. The first column gives the number of parameters needed to describe the model (often referred to as its ‘degrees of freedom’), the second and third columns show how many generic measurements are needed for successful recovery. In ‘nonconvex recovery’, we assume we are able to find the global minimum of a nonconvex problem. This is clearly intractable in general, and not a practical recovery method—we consider it as a benchmark for theoretical comparison with the (tractable) convex relaxation in order to determine how powerful the relaxation is.

This paper describes a general framework for analyzing the recovery of models that have more than one structure, by combining penalty functions corresponding to each structure. The framework proposed includes special cases that are of interest in their own right, e.g., sparse and low-rank matrix recovery and low-rank tensor completion . Our contributions can be summarized as follows.

We consider a model with several structures and associated structure-inducing norms. For recovery, we consider a multi-objective optimization problem to minimize the individual norms simultaneously. Using Pareto optimality, we know that minimizing a weighted sum of the norms and varying the weights traces out all points of the Pareto-optimal front (i.e., the trade-off surface, Section 2). We obtain a lower bound on the number of measurements for any convex function combining the individual norms. A sketch of our main result is as follows.

Given a model $\mathbf{x}_{0}$ with $\tau$ simultaneous structures, the number of measurements required for recovery with high probability using any linear combination of the individual norms satisfies the lower bound

where $m_{i}$ is an intrinsic lower bound on the required number of measurements when minimizing the $i$th norm only. The term $c$ depends on the measurement ensemble we are dealing with.

For the norms of interest, $m_{i}$ will be approximately proportional to the degrees of freedom of the $i$th model, as well as the sample complexity of the associated norm. With $m_{\min}$ as the bottleneck, this result indicates that the combination of norms performs no better than using only one of the norms, even though the target model has a very small degree of freedom.

Our characterization of recovery failure is easy to interpret and deterministic in nature. We show that it can be used to obtain probabilistic failure results for various random measurement ensembles. In particular, our results hold for measurement matrices with i.i.d subgaussian rows, quadratic measurements and matrix completion type measurements.

We characterize the sample complexity of the multi-objective function as a function of the weights associated with the individual norms. Our upper and lower bounds reveal that the sample complexity of the multi-objective function is related to a certain convex combination of the sample complexities associated with the individual norms. We give formulas for this combination as a function of the weights.

In addition, we can incorporate side information on $\mathbf{x}_{0}$, expressed as convex cone constraints. This additional information helps in recovery; however, quantifying how much the cone constraints help is not trivial. Our analysis explicitly determines the role of the cone constraint: Geometric properties of the cone such as its Gaussian width determines the constant factors in the bound on the number of measurements.

As a special case, we consider the recovery of simultaneously sparse and low-rank matrices and prove that there is a significant gap between the performance of convex and non-convex recovery programs. This gap is surprising when one considers similar results in low-dimensional model recovery discussed above in Table 2.

2 Applications

We survey several applications where simultaneous structures arise, as well as existing results specific to these applications. These applications all involve models with simultaneous structures, but the measurement model and the norms that matter differ among applications.

Sparsity has long been exploited in signal processing, applied mathematics, statistics and computer science for tasks such as compression, denoising, model selection, image processing and more. Despite the great interest in exploiting sparsity in various applications, most of the work to date has focused on recovering sparse or low rank data from linear measurements. Recently, the basic sparse recovery problem has been generalized to the case in which the measurements are given by nonlinear transforms of the unknown input, . A special case of this more general setting is quadratic compressed sensing in which the goal is to recover a sparse vector $\mathbf{x}$ from quadratic measurements $b_{i}=\mathbf{x}^{T}\mathbf{A}_{i}\mathbf{x}$. This problem can be linearized by lifting, where we wish to recover a “low rank and sparse” matrix $\mathbf{X}=\mathbf{x}\mathbf{x}^{T}$ subject to measurements $b_{i}=\left<\mathbf{A}_{i},\mathbf{X}\right>$.

Sparse recovery problems from quadratic measurements arise in a variety of problems in optics. One example is sub-wavelength optical imaging in which the goal is to recover a sparse image from its far-field measurements, where due to the laws of physics the relationship between the (clean) measurement and the unknown image is quadratic. In the quadratic relationship is a result of using partially-incoherent light. The quadratic behavior of the measurements in arises from coherent diffractive imaging in which the image is recovered from its intensity pattern. Under an appropriate experimental setup, this problem amounts to reconstruction of a sparse signal from the magnitude of its Fourier transform.

A related and notable problem involving sparse and low-rank matrices is Sparse Principal Component Analysis (SPCA), mentioned in Section 9.

The problem becomes linear when $\mathbf{x}$ is lifted and we consider the recovery of $\mathbf{X}=\mathbf{x}\mathbf{x}^{T}$ where each measurement takes the form $b_{i}^{2}=\left<\mathbf{a}_{i}\mathbf{a}_{i}^{T},\mathbf{X}\right>$. In , an algorithm was developed to treat phase retrieval problems with sparse $\mathbf{x}$ based on a semidefinite relaxation, and low-rank matrix recovery combined with a row-sparsity constraint on the resulting matrix. More recent works also proposed the use of semidefinite relaxation together with sparsity constraints for phase retrieval . An alternative algorithm was recently designed in based on a greedy search. In , the authors also consider sparse signal recovery based on combinatorial and probabilistic approaches and give uniqueness results under certain conditions. Stable uniqueness in phase retrieval problems is studied in . The results of applies to general (non-sparse) signals where in some cases masked versions of the signal are required.

To the best of our knowledge, the sample complexity of fused lasso has not been analyzed from a compressed sensing point of view. However, there is a series of recent work on the total variation minimization, which may lead to analysis of (1.1) in the future .

We remark that TV regularization is also used together with the nuclear norm to encourage a low-rank and smooth (i.e., slowly varying entries) solution. This regularization finds applications in imaging and physics .

Low-rank tensors have applications in machine learning, physics, computational finance and high dimensional PDE’s . (1.2) has been investigated by several papers . Closer to us, recently showed that the convex relaxation (1.2) performs poorly compared to information theoretically optimal bounds for Gaussian measurements. Our results can extend those to the more applicable tensor completion setup, where we observe the entries of the tensor.

Other applications of simultaneously structured signals include Collaborative Hierarchical Sparse Modeling where sparsity is considered within the non-zero blocks in a block-sparse vector, and the recovery of hyperspectral images where we aim to recover a simultaneously block sparse and low rank matrix from compressed observations .

3 Outline of the paper

The paper is structured as follows. Background and definitions are given in Section 2. An overview of the main results is provided in Section 3. Section 4 discusses some measurement ensembles for which our results apply. Section 5 provides upper bounds for the convex relaxations for the Gaussian measurement ensemble. The proofs of the general results are presented in Section 6. The proofs for the special case of simultaneously sparse and low-rank matrices are given in Section 7, where we compare corollaries of the general results with the results on non-convex recovery approaches, and illustrate a gap. Numerical simulations in Section 8 empirically support the results on sparse and low-rank matrices. Future directions of research and discussion of results are in Section 9.

Problem Setup

Given a nonzero vector $\mathbf{x}$ and a set $S$, $\rho(\mathbf{x},S)$ is defined as

$\rho(\mathbf{x},S)$ corresponds to the minimum absolute-valued correlation between the vector $\mathbf{x}$ and elements of $S$. Let ${\bf{\bar{x}}}=\frac{\mathbf{x}}{\|\mathbf{x}\|_{2}}$. The correlation between $\mathbf{x}$ and the associated subdifferential has a simple form.

Here, we used the fact that, for norms, subgradients $\mathbf{g}\in\partial\|\mathbf{x}\|$ satisfy $\mathbf{x}^{T}\mathbf{g}=\|\mathbf{x}\|$, . The denominator of the right hand side is the local Lipschitz constant of $\|\cdot\|$ at $\mathbf{x}$ and is upper bounded by $L$. Consequently, $\rho(\mathbf{x},\partial\|\mathbf{x}\|)\geq\frac{\|{\bf{\bar{x}}}\|}{L}$. We will denote $\frac{\|{\bf{\bar{x}}}\|}{L}$ by $\kappa$. Recently, this quantity has been studied by Mu et al. to analyze the simultaneously structured signals in a similar spirit to us for Gaussian measurements The work is submitted after our initial manuscript; which was projecting the subdifferential onto a carefully chosen subspace to obtain bounds on the sample complexity (see Proposition 6.1). Inspired from , projection onto $\mathbf{x}_{0}$ and the use of $\kappa$ led to the simplification of the notation and improvement of the results in the current manuscript, in particular, Section 4.. Similar calculations as above gives an alternative interpretation for $\kappa$ which is illustrated in Figure 2.

$\kappa$ is a measure of alignment between the vector $\mathbf{x}$ and the subdifferential. For the norms of interest, it is associated with the model complexity. For instance, for a $k$-sparse vector $\mathbf{x}$, $\|{\bf{\bar{x}}}\|_{1}$ lies between $1$ and $\sqrt{k}$ depending on how spiky nonzero entries are. Also $L=\sqrt{n}$. When nonzero entries are $\pm 1$, we find $\kappa^{2}=\frac{k}{n}$. Similarly, given a $d\times d$, rank $r$ matrix $\mathbf{X}$, $\|{\bf{\bar{X}}}\|_{\star}$ lies between $1$ and $\sqrt{r}$. If the singular values are spread (i.e. $\pm 1$), we find $\kappa^{2}=\frac{r}{d}=\frac{rd}{d^{2}}$. In these cases, $\kappa^{2}$ is proportional to the model complexity normalized by the ambient dimension.

1 Convex recovery program

which is convex and has the same Pareto optimal points as the original set (see, e.g., [52, Chapter 4]).

We call $\mathbf{x}_{0}$ recoverable if it is a Pareto optimal point; i.e., there does not exist a feasible $\mathbf{x}^{\prime}\neq\mathbf{x}$ satisfying ${\cal{A}}(\mathbf{x}^{\prime})={\cal{A}}(\mathbf{x}_{0})$ and $\mathbf{x}^{\prime}\in\mathcal{C}$, with $\|\mathbf{x}^{\prime}\|_{(i)}\leq\|\mathbf{x}_{0}\|_{(i)}$ for $i=1,\ldots,\tau\,$.

The vector-valued convex recovery program can be turned into a scalar optimization problem as

In Figure 3, consider the smallest $m$ that makes $\mathbf{x}_{0}$ recoverable. Then one can choose a function $h$ and recover $\mathbf{x}_{0}$ by (2.1) using the $m$ measurements. If the number of measurements is any less, then no function can recover $\mathbf{x}_{0}$. Our goal is to provide lower bounds on $m$.

Note that in , Chandrasekaran et al. propose a general theory for constructing a suitable penalty, called an atomic norm, given a single set of atoms that describes the structure of the target object. In the case of simultaneous structures, this construction requires defining new atoms, and then ensuring the resulting atomic norm can be minimized in a computationally tractable way, which is nontrivial and often intractable. We briefly discuss such constructions as a future research direction in Section 9.

Main Results: Theorem Statements

In this section, we state our main theorems that aim to characterize the number of measurements needed to recover a simultaneously structured signal by convex or nonconvex programs. We first present our general results, followed by results for simultaneously sparse and low-rank matrices as a specific but important instance of the general case. The proofs are given in Sections 6 and 7. All of our statements will implicitly assume $\mathbf{x}_{0}\neq 0$. This will ensure that $\mathbf{x}_{0}$ is not a trivial minimizer and is not in the subdifferentials.

This section deals with the recovery of a signal $\mathbf{x}_{0}$ that is simultaneously structured with $S_{1},S_{2},\dots,S_{\tau}$ as described in Section 2. We give a lower bound on the required number of measurements, using the geometric properties of the individual norms.

Then, $\mathbf{x}_{0}$ is not a minimizer of (2.1).

Theorem 3.1 is deterministic in nature. However, it can be easily specialized to specific random measurement ensembles. The left hand side of (3.1) depends only on the vector $\mathbf{x}_{0}$ and the subdifferential $\partial f(\mathbf{x}_{0})$, hence it is independent of the measurement matrix ${\bf{A}}$. For simultaneously structured models, we will argue that, the left hand side cannot be made too small, as the subgradients are aligned with the signal. On the other hand, the right hand side depends only on ${\bf{A}}$ and $\mathbf{x}_{0}$ and is independent of the subdifferential. In linear inverse problems, ${\bf{A}}$ is often assumed to be random. For large class of random matrices, we will argue that, the right hand side is approximately $\sim\sqrt{\frac{m}{n}}$ which will yield a lower bound on the number of required measurements.

Typical measurement ensembles include the following,

Matrices with i.i.d. rows: ${\bf{A}}$ has independent and identically distributed rows with certain moment conditions. This is a widely used setup in compressed sensing as each measurement we make is associated with the corresponding row of ${\bf{A}}$ .

Quadratic measurements: Arises in the phase retrieval problem as discussed in Section 1.2.

In Section 4, we find upper bounds on the right hand side of (3.1) for these ensembles. As it will be discussed in Section 4, we can do modifications in the rows of ${\bf{A}}$ to get better bounds as long as it does not affect its null space. For instance, one can discard the identical rows to improve conditioning. However, as $m$ increases and ${\bf{A}}$ has more linearly independent rows, $\sigma_{\min}({\bf{A}}^{T})$ will naturally decrease and (3.1) will no longer hold after a certain point. In particular, (3.1) cannot hold beyond $m\geq n$ as $\sigma_{\min}({\bf{A}}^{T})=0$. This is indeed natural as the system becomes overdetermined.

The following proposition lower bounds the left hand side of (3.1) in an interpretable manner. In particular, the correlation $\rho(\mathbf{x}_{0},\partial f(\mathbf{x}_{0}))$ can be lower bounded by the smallest individual correlation.

Let $L_{i}$ be the Lipschitz constant of the $i$’th norm and $\kappa_{i}=\frac{\|{\bf{\bar{x}}}_{0}\|_{(i)}}{L_{i}}$ for $1\leq i\leq\tau$. Set $\kappa_{\min}=\displaystyle\min\{\kappa_{i}:\;i=1,\ldots,\tau\}$. We have the following,

All functions $f(\cdot)$ in (2.1) satisfy, $\rho(\mathbf{x}_{0},\partial f(\mathbf{x}_{0}))\geq\kappa_{\min}$The lower bound $\kappa_{\min}$ is directly comparable to Theorem $5$ of . Indeed, our lower bounds on the sample complexity will have the form $\mathcal{O}\left(\kappa_{\min}^{2}n\right)$..

Suppose $f(\cdot)$ is a weighted linear combination $f(\mathbf{x})=\sum_{i=1}^{\tau}{\lambda}_{i}\|\mathbf{x}\|_{(i)}$ for nonnegative $\{{\lambda}_{i}\}_{i=1}^{\tau}$. Let $\bar{{\lambda}}_{i}=\frac{{\lambda}_{i}L_{i}}{\sum_{i=1}^{\tau}{\lambda}_{i}L_{i}}$ for $1\leq i\leq\tau$. Then, $\rho(\mathbf{x}_{0},\partial f(\mathbf{x}_{0}))\geq\sum_{i=1}^{\tau}\bar{{\lambda}}_{i}\kappa_{i}$.

Proof. From Lemma 6.3, any subgradient of $f(\cdot)$ can be written as, $\mathbf{g}=\sum_{i=1}^{\tau}w_{i}\mathbf{g}_{i}$ for some nonnegative $w_{i}$’s. On the other hand, from , $\left<{\bf{\bar{x}}}_{0},\mathbf{g}_{i}\right>=\|{\bf{\bar{x}}}_{0}\|_{(i)}$. Combining, we find,

From triangle inequality, $\|\mathbf{g}\|_{2}\leq\sum_{i=1}^{\tau}w_{i}L_{i}$. To conclude, we use,

For the second part, we use the fact that for the weighted sums of norms, $w_{i}={\lambda}_{i}$ and subgradients has the form $\mathbf{g}=\sum_{i=1}^{\tau}{\lambda}_{i}\mathbf{g}_{i}$, . Then, substitute $\bar{{\lambda}}_{i}$ for ${\lambda}_{i}$ on the left hand side of (3.2).

Before stating the next result, let us give a relevant definition regarding the average distance between a set and a random vector.

When $\mathcal{M}$ is a cone, we have $0\leq\mathbf{D}(\mathcal{M})\leq\sqrt{n}$. Similar definitions have been used extensively in the literature, such as Gaussian width , statistical dimension and mean width . For notational simplicity, let the normalized distance be ${\bar{\mathbf{D}}}(\mathcal{M})=\frac{\mathbf{D}(\mathcal{M})}{\sqrt{n}}$.

We will now state our result for Gaussian measurements; which can additionally include cone constraints for the lower bound. One can obtain results for the other ensembles by referring to Section 4.

Suppose ${\bf{A}}$ has independent $\mathcal{N}(0,1)$ entries. Whenever $m\leq m_{low}$, $\mathbf{x}_{0}$ will not be a minimizer of any of the recovery programs in (2.1) with probability at least $1-10\exp(-\frac{1}{16}\min\{m_{low},(1-{\bar{\mathbf{D}}}(\mathcal{C}))^{2}n\})$, where

As discussed before, there are various options for the scalarizing function in (2.1), with one choice being the weighted sum of norms. In fact, for a recoverable point $\mathbf{x}_{0}$ there always exists a weighted sum of norms which recovers it. This function is also often the choice in applications, where the space of positive weights is searched for a good combination. Thus, we can state the following theorem as a general result.

Suppose ${\bf{A}}$ has i.i.d $\mathcal{N}(0,1)$ entries and $f(\mathbf{x})=\sum_{i=1}^{\tau}{\lambda}_{i}\|\mathbf{x}\|_{(i)}$ for nonnegative weights $\{{\lambda}_{i}\}_{i=1}^{\tau}$. Whenever $m\leq m_{low}^{\prime}$, $\mathbf{x}_{0}$ will not be a minimizer of the recovery program (2.1) with probability at least $1-10\exp(-\frac{1}{16}\min\{m_{low}^{\prime},(1-{\bar{\mathbf{D}}}(\mathcal{C}))^{2}n\})$, where

and $\bar{{\lambda}}_{i}=\frac{{\lambda}_{i}L_{i}}{\sum_{i=1}^{\tau}{\lambda}_{i}L_{i}}$.

Observe that Theorem 3.2 is stronger than stating “a particular function $h(\|\mathbf{x}\|_{(1)},\dots,\|\mathbf{x}\|_{(\tau)})$ will not work”. Instead, our result states that with high probability none of the programs in the class (2.1) can return $\mathbf{x}_{0}$ as the optimal unless the number of measurements are sufficiently large.

To understand the result better, note that the required number of measurements is proportional to $\kappa_{min}^{2}n$ which is often proportional to the sample complexity of the best individual norm. As we have argued in Section 2, $\kappa_{i}^{2}n$ corresponds to how structured the signal is. For sparse signals it is equal to the sparsity, and for a rank $r$ matrix, it is equal to the degrees of freedom of the set of rank $r$ matrices. Consequently, Theorem 3.2 suggests that even if the signal satisfies multiple structures, the required number of measurements is effectively determined by only one dominant structure.

Intuitively, the degrees of freedom of a simultaneously structured signal can be much lower, which is provable for the S&L matrices. Hence, there is a considerable gap between the expected measurements based on model complexity and the number of measurements needed for recovery via (2.1) ($\kappa_{\min}^{2}n$).

2 Simultaneously Sparse and Low-rank Matrices

We now focus on a special case, namely simultaneously sparse and low-rank (S$\&$L) matrices. We consider matrices with nonzero entries contained in a small submatrix where the submatrix itself is low rank. Here, norms of interest are $\|\cdot\|_{1,2}$, $\|\cdot\|_{1}$ and $\|\cdot\|_{\star}$ and the cone of interest is the PSD cone. We also consider nonconvex approaches and contrast the results with convex approaches. For the nonconvex problem, we replace the norms $\|\cdot\|_{1},\|\cdot\|_{1,2},\|\cdot\|_{\star}$ with the functions $\|\cdot\|_{0},\|\cdot\|_{0,2},\text{rank}(\cdot)$ which give the number of nonzero entries, the number of nonzero columns and rank of a matrix respectively and use the same cone constraint as the convex method. We show that convex methods perform poorly as predicted by the general result in Theorem 3.2, while nonconvex methods require optimal number of measurements (up to a logarithmic factor). Proofs are given in Section 7.

Based on the results in Section 3.1, we obtain lower bounds on the number of measurements for convex recovery. We additionally show that significantly fewer measurements are sufficient for non-convex programs to uniquely recover $\mathbf{X}_{0}$; thus proving a performance gap between convex and nonconvex approaches. The following theorem summarizes the results.

For the cases given in Definition 3.2, the following convex and nonconvex recovery results hold for some positive constants $c_{1},c_{2}$.

The nonconvex programs require almost the same number of measurements as the degrees of freedom (or number of parameters) of the underlying model. For instance, it is known that the degrees of freedom of a rank $r$ matrix of size $k_{1}\times k_{2}$ is simply $r(k_{1}+k_{2}-r)$ which is $\mathcal{O}\left((k_{1}+k_{2})r\right)$. Hence, the nonconvex results are optimal up to a logarithmic factor. On the other hand, our results on the convex programs that follow from Theorem 3.2 show that the required number of measurements are significantly larger. Table 3 provides a quick comparison of the results on S&L.

For the S&L (k,k,r) model, from standard results one can easily deduce that ,

Nuclear norm penalty only: requires at least $rd$ measurements.

As we saw in Section 3.1, adding a cone constraint to the recovery program does not help in reducing the lower bound by more than a constant factor. In particular, we discuss the positive semidefiniteness assumption that is beneficial in the sparse phase retrieval problem,, and show that the number of measurements remain high even when we include this extra information. On the other hand, the nonconvex recovery programs performs well even without the PSD constraint.

We remark that, we could have stated Theorem 3.3 for more general measurements given in Section 4 without the cone constraint. For instance, the following result holds for the weighted linear combination of individual norms and for the subgaussian ensemble.

(3.3) fails with probability $1-4\exp(-c_{2}m_{low})$. Here $c_{1},c_{2}>0$ are constants as described in Proposition 4.1.

Remark: Choosing $\mathbf{X}_{0}=\mathbf{a}\mathbf{a}^{T}$ where nonzero entries of $\mathbf{a}$ are $\pm 1$ yields $\frac{1}{2}(\beta k+(1-\beta)\sqrt{d})^{2}$ on the right hand side. An explicit construction of an S&L matrix with maximal $\|{\bar{\mathbf{X}}}\|_{1},\|{\bar{\mathbf{X}}}\|_{\star}$ is provided in Section 7.3.

This corollary compares well with the upper bound obtained in Corollary 5.1 of Section 5. In particular, both the bounds and the penalty parameters match up to logarithmic factors. Hence, together, they sandwich the sample complexity of the combined cost $f(\mathbf{X})$.

Measurement ensembles

This section will make use of standard results on sub-gaussian random variables and random matrix theory to obtain probabilistic statements. We will explain how one can analyze the right hand side of (3.1) for,

Subsampled standard basis (in matrix completion),

Quadratic measurements arising in phase retrieval.

We first consider the measurement maps with sub-gaussian entries. The following definitions are borrowed from .

A random variable $x$ is sub-gaussian if there exists a constant $K>0$ such that for all $p\geq 1$,

Suppose ${\bf{A}}$ has i.i.d rows in either of the following forms,

have independent zero-mean unit variance sub-gaussian entries.

Then, there exists constants $c_{1},c_{2}$ depending only on the sub-gaussian norm of the rows, such that, whenever $m\leq c_{1}n$, with probability $1-4\exp(-c_{2}m)$, we have,

Proof. Using Theorem 5.58 of , there exists constants $c,C$ depending only on the sub-gaussian norm of $\mathbf{a}$ such that for any $t\geq 0$, with probability $1-2\exp(-ct^{2})$

Choosing $t=C\sqrt{m}$ and $m\leq\frac{n}{100C^{2}}$ would ensure $\sigma_{\min}({\bf{A}}^{T})\geq\frac{4\sqrt{n}}{5}$.

The second statement can be proved in the exact same manner by using Theorem 5.39 of instead of Theorem 5.58.

2 Randomly sampling entries

We now consider the scenario where each row of ${\bf{A}}$ is chosen from the standard basis uniformly at random. Note that, when $m$ is comparable to $n$, there is a nonnegligible probability that ${\bf{A}}$ will have duplicate rows. Theorem 3.1 does not take this situation into account which would make $\sigma_{\min}({\bf{A}}^{T})=0$. In this case, one can discard the copies as they don’t affect the recoverability of $\mathbf{x}_{0}$. This would get rid of the ill-conditioning, as the new matrix is well-conditioned with the exact same null space as the original, and would correspond to a “sampling without replacement” scheme where we ensure each row is different.

Similar to achievability results in matrix completion , the following failure result requires true signal to be incoherent with the standard basis, where incoherence is characterized by $\|{\bf{\bar{x}}}_{0}\|_{\infty}$, which lies between $\frac{1}{\sqrt{n}}$ and $1$.

Proof. Let $\hat{{\bf{A}}}$ be the matrix obtained by discarding the rows of ${\bf{A}}$ that occur multiple times except one of them. Clearly $\text{Null}(\hat{{\bf{A}}})=\text{Null}({\bf{A}})$ hence they are equivalent for the purpose of recovering $\mathbf{x}_{0}$. Furthermore, $\sigma_{\min}(\hat{{\bf{A}}})=1$. Hence, we are interested in upper bounding $\|\hat{{\bf{A}}}{\bf{\bar{x}}}_{0}\|_{2}$.

Clearly $\|\hat{{\bf{A}}}{\bf{\bar{x}}}_{0}\|_{2}\leq\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}$. Hence, we will bound $\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}^{2}$ probabilistically. Let $\mathbf{a}$ be the first row of ${\bf{A}}$. $|\mathbf{a}^{T}{\bf{\bar{x}}}_{0}|^{2}$ is a random variable, with mean $\frac{1}{n}$ and is upper bounded by $\|{\bf{\bar{x}}}_{0}\|_{\infty}^{2}$. Hence, applying the Chernoff Bound would yield,

Setting $\delta=1$, we find that, with probability $1-\exp(-\frac{m}{4n\|{\bf{\bar{x}}}_{0}\|_{\infty}^{2}})$, we have,

A significant application of this result would be for the low-rank tensor completion problem, where we randomly observe some entries of a low-rank tensor and try to reconstruct it. A promising approach for this problem is using the weighted linear combinations of nuclear norms of the unfoldings of the tensor to induce the low-rank tensor structure described in (1.2), . Related work shows the poor performance of (1.2) for the special case of Gaussian measurements. Combination of Theorem 3.1 and Proposition 4.2 will immediately extend the results of to the more applicable tensor completion setup (under proper incoherence conditions that bound $\|{\bf{\bar{x}}}_{0}\|_{\infty}$).

Remark: In Propositions 4.1 and 4.2, we can make the upper bound for the ratio $\frac{\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}^{2}}{\sigma_{\min}({\bf{A}})^{2}}$ arbitrarily close to $\frac{m}{n}$ by changing the proof parameters. Combined with Proposition 3.1, this would suggest that, failure happens, when $m<n\kappa_{\min}$.

3 Quadratic measurements

Proof. Let $\mathbf{V}_{i}=\mathbf{v}_{i}\mathbf{v}_{i}^{T}$. Without loss of generality, assume $\mathbf{v}_{i}$’s are uniformly distributed over sphere with radius $\sqrt{d}$. To lower bound $\sigma_{\min}({\bf{A}}^{T})$, we will estimate the coherence of its columns, defined by,

Section 5.2.5 of states that sub-gaussian norm of $\mathbf{v}_{i}$ is bounded by an absolute constant. Hence, conditioned on $\mathbf{v}_{j}$ (which satisfies $\|\mathbf{v}_{j}\|_{2}=\sqrt{d}$), $\frac{(\mathbf{v}_{i}^{T}\mathbf{v}_{j})^{2}}{d}$ is a subexponential random variable with mean $1$. Hence, using Definition 4.1, there exists a constant $c>0$ such that,

Union bounding over all $i,j$ pairs ensure that with probability $ed^{-2}$ we have $\mu({\bf{A}}^{T})\leq c\frac{\log d}{d}$. Next, we use the standard result that for a matrix with columns of equal length, $\sigma_{\min}({\bf{A}}^{T})\geq d(1-(m-1)\mu)$. The reader is referred to Proposition 1 of . Hence, $m\leq\frac{d}{2c\log d}$, gives $\sigma_{\min}({\bf{A}}^{T})\geq\frac{d}{2}$.

It remains to upper bound $\|{\cal{A}}({\bf{\bar{X}}}_{0})\|_{2}\,$. The $i$’th entry of ${\cal{A}}({\bf{\bar{X}}}_{0})$ is equal to $|\mathbf{v}_{i}^{T}\bar{\mathbf{a}}|^{2}$, hence it is subexponential. Consequently, there exists a constant $c^{\prime}$ so that each entry is upper bounded by $\frac{c^{\prime}}{2}\log d$ with probability $1-ed^{-3}$. Union bounding, and using $m\leq d$, we find that $\|{\cal{A}}({\bf{\bar{X}}}_{0})\|_{2}\leq\frac{c^{\prime}}{2}\sqrt{m}\log d$ with probability $1-ed^{-2}$. Combining with the $\sigma_{\min}({\bf{A}}^{T})$ estimate we can conclude.

When $\bar{\mathbf{a}}$ is a $k$-sparse vector with $\pm 1$ entries, in a similar flavor to Theorem 3.3, the right hand side has the form $\frac{c}{\log^{2}d}\min\{k^{2},d\}$.

We should emphasize that the lower bound provided in is directly comparable to our results. Authors in consider the same problem and give two results: first, if $m\geq\mathcal{O}\left(\|\bar{\mathbf{a}}\|_{1}^{2}k\log d\right)$ then minimizing $\|\mathbf{X}\|_{1}+\lambda\operatorname{tr}\left(\mathbf{X}\right)$ for suitable value of $\lambda$ over the set of PSD matrices will exactly recover $\mathbf{X}_{0}$ with high probability. Secondly, their Theorem 1.3 gives a necessary condition (lower bound) on the number of measurements, under which the recovery program fails to recover $\mathbf{X}_{0}$ with high probability. In particular, their failure condition is $m\leq\min\{m_{0},\frac{d}{40\log d}\}$ where $m_{0}=\frac{\max(\|\bar{\mathbf{a}}\|_{1}^{2}-k/2,0)^{2}}{500\log^{2}d}$.

First, observe that both results have $m\leq\mathcal{O}\left(\frac{d}{\log d}\right)$ condition. Focusing on the sparsity requirements, when the nonzero entries are sufficiently diffused (i.e. $\|\mathbf{a}\|_{1}^{2}\approx k$) both results yield $\mathcal{O}\left(\frac{\|\bar{\mathbf{a}}\|^{4}}{\log^{2}d}\right)$ as a lower bound. On the other hand, if $\|\bar{\mathbf{a}}\|_{1}\leq\sqrt{\frac{k}{2}}$, their lower bound disappears while our lower bound still requires $\mathcal{O}\left(\frac{\|\bar{\mathbf{a}}\|^{4}}{\log^{2}d}\right)$ measurements. $\|\bar{\mathbf{a}}\|_{1}\leq\sqrt{\frac{k}{2}}$ can happen as soon as the nonzero entries are rather spiky, i.e. some of the entries are much larger than the rest. In this sense, our bounds are tighter. On the other hand, their lower bound includes the PSD constraint unlike ours.

4 Asymptotic regime

While we discussed two cases in the nonasymptotic setup, we believe significantly more general results can be stated asymptotically ($m,n\rightarrow\infty$). For instance, under finite fourth moment constraint, thanks to Bai-Yin law , asymptotically, the smallest singular value of a matrix with i.i.d. unit variance entries concentrate around $\sqrt{n}-\sqrt{m}$. Similarly, $\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}^{2}$ is sum of independent variables; hence thanks to the law of large numbers, we will have $\frac{\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}^{2}}{m}\rightarrow 1$. Together, these yield $\frac{\|{\bf{A}}{\bf{\bar{x}}}_{0}\|_{2}}{\sigma_{\min}({\bf{A}}^{T})}\rightarrow\frac{\sqrt{m}}{\sqrt{n}-\sqrt{m}}$.

Upper bounds

We now state an upper bound on the simultaneous optimization for Gaussian measurement ensemble. Our upper bound will be in terms of distance to the dilated subdifferentials.

Suppose ${\bf{A}}$ has i.i.d. $\mathcal{N}(0,1)$ entries and let $f(\mathbf{x})=\sum_{i=1}^{\tau}{\lambda}_{i}\|\mathbf{x}\|_{(i)}$. For positive scalars $\{{\alpha}_{i}\}_{i=1}^{\tau}$, let ${\bar{{\lambda}}}_{i}=\frac{{\lambda}_{i}{\alpha}_{i}^{-1}}{\sum_{i=1}^{\tau}{\lambda}_{i}{\alpha}_{i}^{-1}}$ and define,

If $m\geq(\sqrt{m_{up}}+t)^{2}+1$, then program (2.1) will succeed with probability $1-2\exp(-\frac{t^{2}}{2})$.

Proof. Fix $\mathbf{h}$ as an i.i.d. standard normal vector. Let $\mathbf{g}_{i}$ be so that $\alpha_{i}\mathbf{g}_{i}$ is closest to $\mathbf{h}$ over $\alpha_{i}\partial\|\mathbf{x}_{0}\|_{(i)}$. Let $\gamma=(\sum_{i}\frac{{\lambda}_{i}}{{\alpha}_{i}})^{-1}$. Then, we may write,

Taking the expectations of both sides and using the definition of $\mathbf{D}(\cdot)$, we find,

Using definition of $\mathbf{D}(\cdot)$, this gives, $m_{up}\geq\mathbf{D}(\text{cone}(\partial f(\mathbf{x}_{0})))^{2}$. The result then follows from the fact that, when $m\geq(\mathbf{D}(\text{cone}(\partial f(\mathbf{x}_{0})))+t)^{2}+1$, recovery succeeds with probability $1-2\exp(-\frac{t^{2}}{2})$. To see this, first, as discussed in Proposition $3.6$ of , $\mathbf{D}(\text{cone}(\partial f(\mathbf{x}_{0})))$ is equal to the Gaussian width of the “tangent cone intersected with the unit ball” (see Theorem A.2 for a definition of Gaussian width). Then, Corollary $3.3$ of yields the probabilistic statement.

For Theorem 5.1 to be useful, choices of ${\alpha}_{i}$ should be made wisely. An obvious choice is letting,

With this choice, our upper bounds can be related to the individual sample complexities, which is equal to $\mathbf{D}(\text{cone}(\partial\|\mathbf{x}_{0}\|_{(i)}))^{2}$. Proposition $1$ of shows that, if $\|\cdot\|_{(i)}$ is a decomposable norm, then,

Suppose ${\bf{A}}$ has i.i.d $\mathcal{N}(0,1)$ entries and let $f(\mathbf{x})=\sum_{i=1}^{\tau}{\lambda}_{i}\|\mathbf{x}\|_{(i)}$ for decomposable norms $\{\|\cdot\|_{(i)}\}_{i=1}^{\tau}$. Let $\{{\alpha}_{i}^{*}\}_{i=1}^{\tau}$ be as in (5.1) and assume they are strictly positive. Let ${\bar{{\lambda}}}_{i}^{*}=\frac{{\lambda}_{i}({\alpha}_{i}^{*})^{-1}}{\sum_{i=1}^{\tau}{\lambda}_{i}({\alpha}_{i}^{*})^{-1}}$ and define,

If $m\geq(\sqrt{m_{up}}+t)^{2}+1$, then program (2.1) will succeed with probability $1-2\exp(-\frac{t^{2}}{2})$.

Here, we used the fact that $\sum_{i}{\bar{{\lambda}}}_{i}^{*}=1$ to take $6$ out of the sum over $i$. We note that Corollaries 3.1 and 5.1 can be related in the case of sparse and low-rank matrices. For norms of interest, roughly speaking,

$n\kappa_{i}^{2}$ is proportional to the sample complexity $\mathbf{D}(\text{cone}(\partial\|\mathbf{x}_{0}\|_{(i)}))^{2}$.

$L_{i}$ is proportional to $\frac{\sqrt{n}}{{\alpha}_{i}^{*}}$.

Consequently, the sample complexity of (2.1) will be upper and lower bounded by similar convex combinations.

We will now apply the bound obtained in Theorem 5.1 for S&L matrices. To obtain simple and closed form bounds, we will make use of the existing results in the literature.

$\mathbf{X}_{0}$ can be recovered via (2.1) with probability $1-2\exp(-\frac{t^{2}}{2})$.

General Simultaneously Structured Model Recovery

The following definitions will be helpful for the rest of our discussion. For a subspace $M$, denote its orthogonal complement by ${M^{\perp}}$. For a convex set $M$ and a point $\mathbf{x}$, we define the projection operator as

Given a cone $\mathcal{C}$, denote its dual cone by $\mathcal{C}^{*}$ and polar cone by ${\mathcal{C}^{\circ}}=-\mathcal{C}^{*}$, where $\mathcal{C}^{*}$ is defined as

We first show that the objective function $\max_{1\leq i\leq\tau}\frac{\|\mathbf{x}\|_{(i)}}{\|\mathbf{x}_{0}\|_{(i)}}$ can be viewed as the ‘best’ among the functions mentioned in (2.1) for recovery of $\mathbf{x}_{0}$.

Consider the class of recovery programs in (2.1). If the program

fails to recover $\mathbf{x}_{0}$, then any member of this class will also fail to recover $\mathbf{x}_{0}$.

Proof. Suppose (6.1) does not have $\mathbf{x}_{0}$ as an optimal solution and there exists $\mathbf{x}^{\prime}$ such that $f_{\text{\rm best}}(\mathbf{x}^{\prime})\leq f_{\text{\rm best}}(\mathbf{x}_{0})$, then

Conversely, given (6.2), we have $f_{\text{\rm best}}(\mathbf{x}^{\prime})\leq f_{\text{\rm best}}(\mathbf{x}_{0})$ from the definition of $f_{\text{\rm best}}$.

Furthermore, since we assume $h(\cdot)$ in (2.1) is non-decreasing in its arguments and increasing in at least one of them, (6.2) implies $f(\mathbf{x}^{\prime})\leq f(\mathbf{x}_{0})$ for any such function $f(\cdot)$. Thus, failure of $f_{\text{\rm best}}(\cdot)$ in recovery of $\mathbf{x}_{0}$ implies failure of any other function in (2.1) in this task.

The following lemma gives necessary conditions for $\mathbf{x}_{0}$ to be a minimizer of the problem (2.1).

If $\mathbf{x}_{0}$ is a minimizer of the program (2.1), then there exist $\mathbf{v}\in\mathcal{C}^{*}$, $\mathbf{z}$, and $\mathbf{g}\in\partial f(\mathbf{x}_{0})$ such that

The proof of Lemma 6.2 follows from the KKT conditions for (2.1) to have $\mathbf{x}_{0}$ as an optimal solution [53, Section 4.7].

The next lemma describes the subdifferential of any general function $f(\mathbf{x})=h(\|\mathbf{x}\|_{(1)},\dots,\|\mathbf{x}\|_{(\tau)})$ as discussed in Section 2.1.

For any subgradient of the function $f(\mathbf{x})=h(\|\mathbf{x}\|_{(1)},\dots,\|\mathbf{x}\|_{(\tau)})$ at $\mathbf{x}\neq 0$ defined by convex function $h(\cdot)$, there exists non-negative constants $w_{i}$, $i=1,\ldots,\tau$ such that

where $\mathbf{g}_{i}\in\partial\|\mathbf{x}_{0}\|_{(i)}\,$.

Proof. Consider the function $N(\mathbf{x})=\begin{bmatrix}\|\mathbf{x}\|_{(1)},&\dots,&\|\mathbf{x}\|_{(\tau)}\end{bmatrix}^{T}$ by which we have $f(\mathbf{x})=h(N(\mathbf{x}))$. By Theorem 10.49 in we have

where we used the convexity of $f$ and $h$. Now notice that any $\mathbf{y}\in\partial h(N(\mathbf{x}))$ is a non-negative vector because of the monotonicity assumption on $h(\cdot)$. This implies that any subgradient $\mathbf{g}\in\partial f(\mathbf{x})$ is in the form of $\partial(\mathbf{w}^{T}N(\mathbf{x}))$ for some nonnegative vector $\mathbf{w}$. The desired result simply follows because subgradients of conic combination of norms are conic combinations of their subgradients, (see e.g. ).

Using Lemmas 6.2 and 6.3, we now provide the proofs of Theorems 3.1 and 3.2.

2 Proof of Theorem 3.1

Let $\sigma_{\mathcal{C}}(\mathbf{A}^{T})=\inf_{\|\mathbf{z}\|_{2}=1}\frac{\|\mathcal{P}_{\mathcal{C}}({\bf{A}}^{T}\mathbf{z})\|_{2}}{\|{\bf{A}}^{T}\mathbf{z}\|_{2}}$. Let $\cal{R}$ be an arbitrary linear subspace orthogonal to the following cone,

Then, $\mathbf{x}_{0}$ is not a minimizer of (2.1).

and $\left<\mathbf{x}_{0},\mathbf{v}\right>=0\,$. We will first eliminate the contribution of $\mathbf{v}$ in equation (6.4). Projecting both sides of (6.4) onto the subspace $\mathcal{R}$ gives,

Since $\mathbf{v}\in\mathcal{C}^{*}$, from Lemma A.1 we have $\mathcal{P}_{\mathcal{C}}(-\mathbf{v})=\mathcal{P}_{\mathcal{C}}({\bf{A}}^{T}\mathbf{z}-\mathbf{g})=0$. Using Corollary A.1,

Combining (6.7) and (6.8) yields $\|\mathbf{g}\|_{2}\geq\sigma_{\mathcal{C}}({\bf{A}}^{T})\|{\bf{A}}^{T}\mathbf{z}\|_{2}$. Further incorporating (6.6), we find,

Hence, if $\mathbf{x}_{0}$ is recoverable, there exists $\mathbf{g}\in\partial f(\mathbf{x}_{0})$ satisfying,

3 Proof of Theorem 3.2

Rotational invariance of Gaussian measurements allow us to make full use of Proposition 6.1. The following is a generalization of Theorem 3.2.

Consider the setup in Proposition 6.1 where ${\bf{A}}$ has i.i.d $\mathcal{N}(0,1)$ entries. Let,

and suppose $\dim({\cal{R}})\leq m_{low}$. Then, whenever $m\leq m_{low}$, with probability $1-10\exp(-\frac{1}{16}\min\{m_{low},(1-{\bar{\mathbf{D}}}(\mathcal{C}))^{2}n\})$, (2.1) will fail for all functions $f(\cdot)$.

Proof. More measurements can only increase the chance of success. Hence, without losing generality, assume $m=m_{low}$ and $\text{dim}({\cal{R}})\leq m$. The result will follow from Proposition 6.1. Recall that $m\leq\frac{(1-{\bar{\mathbf{D}}}(\mathcal{C}))n}{100}$.

$\mathcal{P}_{\cal{R}}({\bf{A}}^{T})$ is statistically identical to a $\text{dim}({\cal{R}})\times m$ matrix with i.i.d. $\mathcal{N}(0,1)$ entries under proper unitary rotation. Hence, using Corollary 5.35 of , with probability $1-2\exp(-\frac{m}{8})$, $\sigma_{\max}(\mathcal{P}_{\cal{R}}({\bf{A}}^{T}))\leq 1.5\sqrt{m}+\sqrt{\text{dim}({\cal{R}})}\leq 2.5\sqrt{m}$. With the same probability, $\sigma_{\min}({\bf{A}}^{T})\geq\sqrt{n}-1.5\sqrt{m}$.

From Theorem A.3, using $m\leq\frac{(1-{\bar{\mathbf{D}}}(\mathcal{C}))n}{100}$, with probability $1-6\exp(-\frac{(1-{\bar{\mathbf{D}}}(\mathcal{C}))^{2}n}{16})$, $\sigma_{\mathcal{C}}^{2}({\bf{A}}^{T})\geq\frac{1-{\bar{\mathbf{D}}}(\mathcal{C})}{4(1+{\bar{\mathbf{D}}}(\mathcal{C}))}\geq\frac{1-{\bar{\mathbf{D}}}(\mathcal{C})}{8}$.

Since $\frac{m}{n}\leq\frac{1}{30}$, combining these, with the desired probability,

Finally, using Proposition 6.1 and $m\leq\frac{n(1-{\bar{\mathbf{D}}}(\mathcal{C}))}{100}\rho({\cal{R}},\partial f(\mathbf{x}_{0}))^{2}$, with the same probability (2.1) fails.

To achieve Theorem 3.2, choose ${\cal{R}}=\text{span}(\{\mathbf{x}_{0}\})$ and use the first statement of Proposition 3.1.

To achieve Corollary 3.1, choose ${\cal{R}}=\text{span}(\{\mathbf{x}_{0}\})$ and use the second statement of Proposition 3.1.

4 Enhanced lower bounds

Indeed, Proposition 6.1 gives such a bound with a better choice of ${\cal{R}}$. In particular, let us choose ${\cal{R}}=\text{span}(\{\text{sign}(\mathbf{x}_{0})\})$. For any $\mathbf{g}\in\partial\|\mathbf{x}_{0}\|_{1}$, we have that,

Hence, we immediately have $m\geq\mathcal{O}\left(k\right)$ as a lower bound. The idea of choosing such sign vectors can be generalized to the so-called decomposable norms.

We refer to $T$ as the support and $\mathbf{e}$ as the sign vector of $\mathbf{x}$ with respect to $\|\cdot\|\,$.

Similar definitions are used in and . Our definition is simpler and less strict compared to these works. Note that $L$ is a global property of the norm while $\mathbf{e}$ and $T$ depend on both the norm and the point under consideration (decomposability is a local property in this sense).

The next lemma shows that the sign vector $\mathbf{e}$ will yield the largest correlation with the subdifferential and the best lower bound for such norms.

Let $\|\cdot\|$ be a decomposable norm with support $T$ and sign vector $\mathbf{e}$. For any $\mathbf{v}\neq 0$, we have that,

Also $\rho({\mathbf{e}},\partial\|\mathbf{x}_{0}\|)\geq\frac{\|\mathbf{e}\|_{2}}{L}$.

Proof. Let $\mathbf{v}$ be a unit vector. Without losing generality, assume $\mathbf{v}^{T}\mathbf{e}\geq 0$. Pick a vector $\mathbf{z}\in T^{\perp}$ with $\|\mathbf{z}\|^{*}=1$ such that $\mathbf{z}^{T}\mathbf{v}\leq 0$ (otherwise pick $-\mathbf{z}$). Now, consider the class of subgradients $\mathbf{g}(\alpha)=\mathbf{e}+\alpha\mathbf{z}$ for $1\geq\alpha\geq-1$. Then,

If $|\mathbf{z}^{T}\mathbf{v}|\geq\mathbf{e}^{T}\mathbf{v}$, then, the numerator can be made and $\rho(\mathbf{v},\partial\|\mathbf{x}_{0}\|)=0$. Otherwise, the right hand side is decreasing function of $\alpha$, hence the minimum is achieved at $\alpha=1$, which gives,

where we used $\mathbf{e}^{T}\mathbf{g}(\alpha)=\mathbf{e}^{T}\mathbf{e}=\|\mathbf{e}\|^{2}_{2}$. Hence, along any direction $\mathbf{z}$, $\mathbf{e}$ yields a higher minimum correlation than $\mathbf{v}$. To obtain (6.9), further take infimum over all $\mathbf{z}\in T^{\perp},\|\mathbf{z}\|^{*}\leq 1$ which will yield infimum over $\partial\|\mathbf{x}_{0}\|$. Finally, use $\|g(\alpha)\|_{2}\leq L$ to lower bound $\rho({\mathbf{e}},\partial\|\mathbf{x}_{0}\|)$.

Based on Lemma 6.5, the individual lower bound would be $\mathcal{O}\left(\frac{\|\mathbf{e}\|_{2}^{2}}{L^{2}}\right)n$. Calculating $\frac{\|\mathbf{e}\|_{2}^{2}}{L^{2}}n$ for the norms in Lemma 6.4, reveals that, this quantity is $k$ for a $k$ sparse vector, $cd_{1}$ for a $c$-column sparse matrix and $r\max\{d_{1},d_{2}\}$ for a rank $r$ matrix. Compared to bounds obtained by using ${\bf{\bar{x}}}_{0}$, these new quantities are directly proportional to the true model complexities. Finally, we remark that, these new bounds correspond to choosing $\mathbf{x}_{0}$ that maximizes the value of $\|{\bf{\bar{x}}}_{0}\|_{1},\|{\bf{\bar{x}}}_{0}\|_{\star}$ or $\|{\bf{\bar{x}}}_{0}\|_{1,2}$ while keeping sparsity, rank or column sparsity fixed. In particular, in these examples, $\mathbf{e}$ has the same sparsity, rank, column sparsity as $\mathbf{x}_{0}$.

The next lemma gives a correlation bound for the combination of decomposable norms as well as a simple lower bound on the sample complexity.

Given decomposable norms $\|\cdot\|_{(i)}$ with supports $T_{i}$ and sign vectors $\mathbf{e}_{i}$. Let $T_{\cap}=\bigcap_{1\leq i\leq\tau}T_{i}$. Choose the subspace ${\cal{R}}$ to be a subset of $T_{\cap}$.

Assume $\left<\mathcal{P}_{{\cal{R}}}(\mathbf{e}_{i}),\mathcal{P}_{{\cal{R}}}(\mathbf{e}_{j})\right>\geq 0$ for all $i,j$ and $\min_{1\leq i\leq\tau}\frac{\|\mathcal{P}_{{\cal{R}}}(\mathbf{e}_{i})\|_{2}}{\|\mathbf{e}_{i}\|_{2}}\geq\upsilon$. Then,

Consider Proposition 6.1 with Gaussian measurements and suppose ${\cal{R}}$ is orthogonal to the set (6.3). Let $f(\mathbf{x})=\sum_{i=1}^{\tau}{\lambda}_{i}\|\mathbf{x}\|_{(i)}$ for nonnegative $\{{\lambda}_{i}\}$’s. Then, if $m<\text{dim}({\cal{R}})$, (2.1) fails with probability $1$.

Proof. Let $\mathbf{g}=\sum_{i=1}^{\tau}w_{i}\mathbf{g}_{i}$ for some $\mathbf{g}_{i}\in\partial\|\mathbf{x}_{0}\|_{(i)}$. First, $\|\mathbf{g}\|_{2}\leq\sum_{i=1}^{\tau}w_{i}\|\mathbf{g}_{i}\|_{2}$. Next,

To see the second statement, consider the line (6.5) from the proof of Proposition 6.1. $\mathcal{P}_{\cal{R}}(\mathbf{g})=\sum_{i=1}^{\tau}{\lambda}_{i}\mathcal{P}_{\cal{R}}(\mathbf{e}_{i})$. On the other hand, column space of $\mathcal{P}_{\cal{R}}({\bf{A}}^{T})$ is an $m$-dimensional random subspace of ${\cal{R}}$. If $m<\text{dim}({\cal{R}})$, $\mathcal{P}_{\cal{R}}(\mathbf{g})$ is linearly independent with $\mathcal{P}_{\cal{R}}({\bf{A}}^{T})$ with probability $1$ and (6.5) will not hold.

In the next section, we will show how better choices of ${\cal{R}}$ (based on the decomposability assumption) can improve the lower bounds for S&L recovery.

Proofs for Section 3.2

Using the general framework provided in Section 3.1, in this section we present the proof of Theorem 3.3, which states various convex and nonconvex recovery results for the S&L models. We start with the proofs of the convex recovery.

In this section, we prove the statements of Theorem 3.3 regarding convex approaches, using Theorem 3.2 and Proposition 6.2. We will make use of the decomposable norms to obtain better lower bounds. Hence, we first state a result on the sign vectors and the supports of the S&L model following Lemma 6.4. The proof is provided in Appendix B.

$\mathbf{E}_{\star},\mathbf{E}_{r},\mathbf{E}_{c}\in T_{\star}\cap T_{c}\cap T_{r}$,

$\left\langle\mathbf{E}_{\star},\mathbf{E}_{r}\right\rangle\geq 0$, $\left\langle\mathbf{E}_{\star},\mathbf{E}_{c}\right\rangle\geq 0$, and $\left\langle\mathbf{E}_{c},\mathbf{E}_{r}\right\rangle\geq 0$.

If $m<\text{dim}({\cal{R}})$, we have failure with probability $1$. Hence, assume $m\geq\text{dim}({\cal{R}})$. Now, apply Proposition 6.2 with the given $m_{low}$.

1.2 Proof of Corollary 3.2

2 Nonconvex recovery results for S&L

While Theorem 3.3 states the result for Gaussian measurements, we prove the nonconvex recovery for the more general sub-gaussian measurements. We first state a lemma that will be useful in proving the nonconvex results. The proof is provided in the Appendix C and uses standard arguments.

Observe that the function $f(\mathbf{X})=\frac{\|\mathbf{X}\|_{0,2}}{\|\mathbf{X}_{0}\|_{0,2}}+\frac{\|\mathbf{X}^{T}\|_{0,2}}{\|\mathbf{X}_{0}^{T}\|_{0,2}}+\frac{\text{rank}(\mathbf{X})}{\text{rank}(\mathbf{X}_{0})}$ satisfies the triangle inequality and we have $f(\mathbf{X}_{0})=3$. Hence, if all null space elements $\mathbf{W}\in\text{Null}({\cal{A}})$ satisfy $f(\mathbf{W})>6$, we have

for all feasible $\mathbf{X}$ which implies $\mathbf{X}_{0}$ being the unique minimizer.

Consider the set $M$ of matrices, which are supported over a $6k_{1}\times 6k_{2}$ submatrix with rank at most $6r$. Observe that any $\mathbf{Z}$ satisfying $f(\mathbf{Z})\leq 6$ belongs to $M$. Hence ensuring $\text{Null}({\cal{A}})\cap M=\{0\}$ would ensure $f(\mathbf{W})>6$ for all $\mathbf{W}\in\text{Null}({\cal{A}})$. Since $M$ is a cone, this is equivalent to $\text{Null}({\cal{A}})\cap(M\cap{\mathcal{S}}^{d_{1}\times d_{2}})=\emptyset$. Now, applying Lemma 7.2 with set $M$ and $s_{1}=6k_{1}$, $s_{2}=6k_{2}$, $q=6r$ we find the desired result.

Observe that due to the symmetry constraint,

Hence, the minimization is the same as (a2), the matrix is rank $r$ contained in a $k\times k$ submatrix and we additionally have the positive semidefinite constraint which can only reduce the amount of required measurements compared to (a2). Consequently, the result follows by applying Lemma 7.2, similar to (a2).

Let C=\{\mathbf{X}\neq 0\big{|}f(\mathbf{X})\leq f(\mathbf{X}_{0})\}. Since $\text{rank}(\mathbf{X}_{0})=1$, if $f(\mathbf{X})\leq f(\mathbf{X}_{0})=2$, $\text{rank}(\mathbf{X})=1$. With the symmetry constraint, this means $\mathbf{X}=\pm\mathbf{x}\mathbf{x}^{T}$ for some $l$-sparse $\mathbf{x}$. Observe that $\mathbf{X}-\mathbf{X}_{0}$ has rank at most $2$ and is contained in a $2k\times 2k$ submatrix as $l\leq k$. Let $M$ be the set of matrices that are symmetric and whose support lies in a $2k\times 2k$ submatrix. Using Lemma 7.2 with $q=2$, $s_{1}=s_{2}=2k$, whenever $m\geq ck\log\frac{n}{k}$, with desired probability all nonzero $\mathbf{W}\in M$ will satisfy $\mathcal{A}(\mathbf{W})\neq 0$. Consequently, any $\mathbf{X}\in C$ will have $\mathcal{A}(\mathbf{X})\neq\mathcal{A}(\mathbf{X}_{0})$, hence $\mathbf{X}_{0}$ will be the unique minimizer.

3 Existence of a matrix with large κ𝜅\kappa’s

Using ${\bf{{H}}}_{n}$, our aim will be to construct a $d_{1}\times d_{2}$ $S\&L$ $(k_{1},k_{2},r)$ matrix $\mathbf{X}_{0}$ that satisfy $\|{\bf{\bar{X}}}_{0}\|_{1}^{2}\approx k_{1}k_{2}$, $\|{\bf{\bar{X}}}_{0}\|_{\star}^{2}\approx r$, $\|{\bf{\bar{X}}}_{0}\|_{1,2}^{2}\approx k_{2}$ and $\|{\bf{\bar{X}}}_{0}^{T}\|_{1,2}^{2}\approx k_{1}$. To do this, we will construct a $k_{1}\times k_{2}$ matrix and then plant it into a larger $d_{1}\times d_{2}$ matrix. The following lemma summarizes the construction.

In particular, if $k_{1}\equiv 0~{}(\text{mod}~{}r)$ and $k_{2}$ is an integer power of $2$, then,

In particular, $\|\mathbf{X}_{0}\|_{F}^{2}=\|\mathbf{X}_{0}\|_{1}=k_{1}2^{\lfloor\log_{2}k_{2}\rfloor}$, $\|\mathbf{X}_{0}\|_{1,2}=\sqrt{k_{1}}2^{\lfloor\log_{2}k_{2}\rfloor}$ and $\|\mathbf{X}_{0}^{T}\|_{1,2}=k_{1}2^{\frac{\lfloor\log_{2}k_{2}\rfloor}{2}}$. Substituting these yield the results for these norms.

To lower bound the nuclear norm, observe that, each of the first $r$ rows of the ${\bf{{H}}}$ are repeated at least $\lfloor\frac{k_{1}}{r}\rfloor$ times in $\mathbf{X}$. Combined with the orthogonality, this ensures that each singular value of $\mathbf{X}$ that is associated with the $j$’th row of ${\bf{{H}}}$ is at least $\sqrt{2^{\lfloor\log_{2}k_{2}\rfloor}\lfloor\frac{k_{1}}{r}\rfloor}$ for all $1\leq j\leq r$. Consequently,

Use the fact that $\lfloor\frac{k_{1}}{r}\rfloor\geq\frac{k_{1}}{2r}$ as $k_{1}\geq r$.

If we are allowed to use complex numbers, one can apply the same idea with the Discrete Fourier Transform (DFT) matrix. Similar to ${\bf{{H}}}_{n}$, DFT has orthogonal rows and its entries have the same absolute value. However, it exists for any $n\geq 1$; which would make the argument more concise.

Numerical Experiments

In this section, we numerically verify our theoretical bounds on the number of measurements for the Sparse and Low-rank recovery problem. We demonstrate the empirical performance of the weighted maximum of the norms $f_{\text{\rm best}}$ (see Lemma 6.1), as well as the weighted sum of norms.

The experimental setup is as follows. Our goal is to explore how the number of required measurements $m$ scales with the size of the matrix $d$. We consider a grid of $(m,d)$ values, and generate at least 100 test instances for each grid point (in the boundary areas, we increase the number of instances to at least 200).

We generate the target matrix $\mathbf{X}_{0}$ by generating a $k\times r$ i.i.d. Gaussian matrix $\mathbf{G}$, and inserting the $k\times k$ matrix $\mathbf{G}\mathbf{G}^{T}$ in an $d\times d$ matrix of zeros. We take $r=1$ and $k=8$ in all of the following experiments; even with these small values, we can observe the scaling predicted by our bounds. In each test, we measure the normalized recovery error $\frac{\|\mathbf{X}-\mathbf{X}_{0}\|_{F}}{\|\mathbf{X}_{0}\|_{F}}$ and declare successful recovery when this error is less than $10^{-4}$. The optimization programs are solved using the CVX package , which calls the SDP solver SeDuMi .

We first test our bound in part (b) of Theorem 3.3, $\Omega(rd)$, on the number of measurements for recovery in the case of minimizing $\max\{\frac{\operatorname{tr}\left(\mathbf{X}\right)}{\operatorname{tr}\left(\mathbf{X}_{0}\right)},\frac{\|\mathbf{X}\|_{1,2}}{\|\mathbf{X}_{0}\|_{1,2}}\}$ over the set of positive semi-definite matrices. Figure 5 shows the results, which demonstrates $m$ scaling linearly with $d$ (note that $r=1$).

The penalty function $\max\{\frac{\operatorname{tr}\left(\mathbf{X}\right)}{\operatorname{tr}\left(\mathbf{X}_{0}\right)},\frac{\|\mathbf{X}\|_{1}}{\|\mathbf{X}_{0}\|_{1}}\}$ depends on the norm of $\mathbf{X}_{0}$. In practice the norm of the solution is not known beforehand, a weighted sum of norms is used instead. In Figure 7 we examine the performance of the weighted sum of norms penalty in recovery of a rank-1 PSD matrix, for different weights. We pick $\lambda=0.20$ and $\lambda=0.35$ for a randomly generated matrix $\mathbf{X}_{0}$, and it can be seen that we get a reasonable result which is comparable to the performance of $\max\{\frac{\operatorname{tr}\left(\mathbf{X}\right)}{\operatorname{tr}\left(\mathbf{X}_{0}\right)},\frac{\|\mathbf{X}\|_{1}}{\|\mathbf{X}_{0}\|_{1}}\}$.

In addition, we consider the amount of error in the recovery when the program fails. Figure 8 shows two curves below which we get a $90\%$ percent failure, where for the green curve the normalized error threshold for declaring failure is $10^{-4}$, and for the red curve it is a larger value of $0.05$. We minimize $\max\{\frac{\operatorname{tr}\left(\mathbf{X}\right)}{\operatorname{tr}\left(\mathbf{X}_{0}\right)},\frac{\|\mathbf{X}\|_{1}}{\|\mathbf{X}_{0}\|_{1}}\}$ as the objective. We observe that when the recovery program has an error, it is very likely that this error is large, as the curves for $10^{-4}$ and $0.05$ almost overlap. Thus, when the program fails, it fails badly. This observation agrees with intuition from similar problems in compressed sensing where sharp phase transition is observed.