Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Introduction

Tensors arise naturally in problems where the goal is to estimate a multi-dimensional object whose entries are indexed by several continuous or discrete variables. For example, a video is indexed by two spatial variables and one temporal variable; a hyperspectral datacube is indexed by two spatial variables and a frequency/wavelength variable. While tensors often reside in extremely high-dimensional data spaces, in many applications, the tensor of interest is low-rank, or approximately so [KB09], and hence has much lower-dimensional structure. The general problem of estimating a low-rank tensor has applications in many different areas, both theoretical and applied: e.g., estimating latent variable graphical models [AGH+12], classifying audio [MSS06], mining text [CC12], processing radar signals [DN10], to name a few.

In contrast, the correct generalization of these results to low-rank tensors is not obvious. The numerical algebra of tensors is fraught with hardness results [HL09]. For example, even computing a tensor’s (CP) rank,

is NP-hard in general. The nuclear norm of a tensor is also intractable, and so we cannot simply follow the formula that has worked for vectors and matrices.

With an eye towards numerical computation, many researchers have studied how to estimate or recover tensors of small Tucker rank [Tuc66]. The Tucker rank of a $K$-way tensor ${\boldsymbol{\mathcal{X}}}$ is a $K$-dimensional vector whose $i$-th entry is the (matrix) rank of the mode-$i$ unfolding ${\boldsymbol{\mathcal{X}}}_{(i)}$ of ${\boldsymbol{\mathcal{X}}}$:

The definition (1.2) suggests a very natural, tractable convex approach to recovering low-rank tensors: seek the ${\boldsymbol{\mathcal{X}}}$ that minimizes $\sum_{i}\lambda_{i}\left\|{\boldsymbol{\mathcal{X}}}_{(i)}\right\|_{*}$ out of all ${\boldsymbol{\mathcal{X}}}$ satisfying $\mathcal{G}[{\boldsymbol{\mathcal{X}}}]=\mathbf{z}$. We will refer to this as the sum-of-nuclear-norms (SNN) model. Originally, proposed in [LMWY09], this approach has been widely studied [GRY11, SDS10, THK10, TSHK11, STDLS13] and applied to various datasets in imaging [SVdPDMS11, SHKM13, KS13, LL10, LYZY10].

Our theoretical results pertain to Gaussian operators $\mathcal{G}$. The motivation for studying Gaussian measurements is twofold. First, Gaussian measurements may be of interest for compressed sensing recovery [Don06], either directly as a measurement strategy, or indirectly due to universality phenomena [DT09, BLM12]. Second, the available theoretical tools for Gaussian measurements are very sharp, allowing us to rigorously investigate the efficacy of various regularization schemes, and prove both upper and lower bonds on the number of observations required. In simulation, our qualitative conclusions carry over to more realistic measurement models, such as random subsampling [LMWY09] (see Section 5). We expect our results to be of interest for a wide range of problems in tensor completion [LMWY09], robust tensor recovery / decomposition [LYZY10, GQ12] and sensing.

Our technical methodology draws on, and enriches, the literature on general structured model recovery. The surprisingly poor behavior of the SNN model is an example of a phenomenon first discovered by Oymak et. al. [OJF+12]: for recovering objects with multiple structures, a combination of structure-inducing norms is often not significantly more powerful than the best individual structure-inducing norm. Our lower bound for the SNN model follows from a general result of this nature, which we prove using the geometric framework of [ALMT13]. Compared to [OJF+12], our result pertains to a more general family of regularizers, and gives sharper constants. In addition, we demonstrate the possibility to reduce the number of generic measurements through a new convex regularizer that exploit several sparse structures jointly.

Bounds for Non-Convex Recovery

In this section, we introduce a non-convex model for tensor recovery, and show that it recovers low-rank tensors from near-minimal numbers of measurements. While our nonconvex formulation is computationally intractable, it gives a baseline for evaluating tractable (convex) approaches.

In vector optimization, a feasible point is called Pareto optimal if no other feasible point dominates it in every criterion. In a similar vein, we say that (2.1) recovers ${{\mathbf{\mathcal{X}}}_{0}}$ if there does not exist any other tensor ${\boldsymbol{\mathcal{X}}}$ that is consistent with the observations and has no larger rank along each mode:

We call ${{\mathbf{\mathcal{X}}}_{0}}$ recoverable by (2.1) if the set

This is equivalent to saying that ${{\mathbf{\mathcal{X}}}_{0}}$ is the unique optimal solution to the scalar optimization:

Whenever $m\geq(2r)^{K}+2nrK+1$, with probability one, $\rm{null}(\mathcal{G})\cap\mathfrak{T}_{2r}=\{\mathbf{0}\}$, and hence (2.1) recovers every ${{\mathbf{\mathcal{X}}}_{0}}\in\mathfrak{T}_{r}$.

The proof of Theorem 1 follows from a covering argument, which we establish in several steps. Let

The following lemma shows that the required number of measurements can be bounded in terms of the exponent of the covering number for $\mathfrak{S}_{2r}$, which can be considered as a proxy for dimensionality:

Suppose that the covering number for $\mathfrak{S}_{2r}$ with respect to Frobenius norm, satisfies

It just remains to find the covering number of $\mathfrak{S}_{2r}$. We use the following lemma, which uses the triangle inequality to control the effect of perturbations in the factors of the Tucker decomposition

where the mode-$i$ (matrix) product of tensor ${\boldsymbol{\mathcal{A}}}$ with matrix $\mathbf{B}$ of compatible size, denoted as ${\boldsymbol{\mathcal{A}}}\times_{i}\mathbf{B}$, outputs a tensor ${\boldsymbol{\mathcal{C}}}$ such that ${\boldsymbol{\mathcal{C}}}_{(i)}=\mathbf{B}{\boldsymbol{\mathcal{A}}}_{(i)}$.

Using this result, we construct an $\varepsilon$-net for $\mathfrak{S}_{2r}$ by building $\varepsilon/(K+1)$-nets for each of the $K+1$ factors ${\boldsymbol{\mathcal{C}}}$ and $\{\mathbf{U}_{i}\}$. The total size of the resulting $\varepsilon$ net is thus bounded by the following lemma:

$N(\mathfrak{S}_{2r},\left\|\cdot\right\|_{F},\varepsilon)\;\leq\;\left(3(K+1)/\varepsilon\right)^{(2r)^{K}+2nrK}$

With these observations in hand, Theorem 1 follows immediately.

Convexification: Sum of Nuclear Norms?

Since the nonconvex problem (2.1) is NP-hard for general $\mathcal{G}$, it is tempting to seek a convex surrogate. In matrix recovery problems, the nuclear norm is often an excellent convex surrogate for the rank [Faz02, RFP10, Gro11]. It seems natural, then, to replace the ranks in (2.1) with nuclear norms, and solve

Since $\left\|\mathbf{\mathcal{X}}_{(i)}\right\|_{*}$ is a convex function, the set $\mathcal{H}:=\bigcup_{{\boldsymbol{\mathcal{X}}}:\mathcal{G}[\mathbf{\mathcal{X}}]=\mathcal{G}[{{\mathbf{\mathcal{X}}}_{0}}]}\left\{{\boldsymbol{\mathcal{Y}}}\mid h({\boldsymbol{\mathcal{Y}}})\succeq h(\mathbf{\mathcal{X}})\right\}$ is convex. For any pareto optimal point $\widehat{\mathbf{\mathcal{X}}}$, there is a hyperplane supporting $\mathcal{H}$ passing through $h(\widehat{\mathbf{\mathcal{X}}})$, with normal vector $\mathbf{\lambda}\geq\mathbf{0}$. Therefore, $\widehat{\mathbf{\mathcal{X}}}$ is an optimal solution to the following scalar optimization:

Suppose that ${\boldsymbol{\mathcal{X}}}_{0}$ has Tucker rank $(r,\dots,r)$, and $m\geq Crn^{K-1}$. With high probability, ${\boldsymbol{\mathcal{X}}}_{0}$ is an optimal solution to (3.2), with each $\lambda_{i}=1$. Here, $C$ is numerical.

This result shows that there is a range in which (3.2) succeeds: loosely, when we undersample by at most a factor of $m/N\sim r/n$. However, the number of observations $m\sim rn^{K-1}$ is significantly larger than the number of degrees of freedom in ${\boldsymbol{\mathcal{X}}}_{0}$, which is on the order of $r^{K}+nrK$. Is it possible to prove a better bound for this model? Unfortunately, we show that in general $O(rn^{K-1})$ measurements are also necessary for reliable recovery using (3.2):

Let ${\boldsymbol{\mathcal{X}}}_{0}\in\mathfrak{T}_{r}$ be nonzero. Set $\kappa=\min_{i}\left\{\left\|({\boldsymbol{\mathcal{X}}}_{0})_{(i)}\right\|_{*}^{2}/\left\|{\boldsymbol{\mathcal{X}}}_{0}\right\|_{F}^{2}\right\}\times n^{K-1}$. Then if the number of measurements $m\leq\kappa-2$, ${{\mathbf{\mathcal{X}}}_{0}}$ is not the unique solution to (3.2), with probability at least $1-4\exp(-\frac{(\kappa-m-2)^{2}}{16(\kappa-2)})$. Moreover, there exists ${\boldsymbol{\mathcal{X}}}_{0}\in\mathfrak{T}_{r}$ for which $\kappa=rn^{K-1}$.

This implies that Corollary 2 (and other results of [THK10]) is essentially tight. Unfortunately, it has negative implications for the efficacy of the sum of nuclear norms in (3.2): although a generic element ${\boldsymbol{\mathcal{X}}}_{0}$ of $\mathfrak{T}_{r}$ can be described using at most $r^{K}+nrK$ real numbers, we require $\Omega(rn^{K-1})$ observations to recover it using (3.2). Theorem 3 is a direct consequence of a much more general principle underlying multi-structured recovery, which is elaborated next.

The poor behavior of (3.2) is actually an instance of a much more general phenomenon, first discovered by Oymak et. al. [OJF+12]. Our target tensor ${\boldsymbol{\mathcal{X}}}_{0}$ has multiple low-dimensional structures simultaneously: it is low-rank along each of the $K$ modes. In practical applications, many other such simultaneously structured objects may be of interest – for example, matrices that are simultaneously sparse and low-rank [RSV12, OJF+12]. To recover such a simultaneously structured object, it is tempting to build a convex relaxation by combining the convex relaxations for each of the individual structures. In the tensor case, this yields (3.2). Surprisingly, this combination is often not significantly more powerful than the best single regularizer [OJF+12]. We obtain Theorem 3 as a consquence of a new, general result of this nature, using a geometric framework introduced in [ALMT13]. Compared to the proof strategy in [OJF+12], this approach has a clearer geometric intuition, covers a more general class of regularizers and yields sharper bounds.

where $\mathcal{G}[\cdot]$ is a Gaussian measurement operator, and $\mathbf{\lambda}>\mathbf{0}$. Is $\mathbf{x}_{0}$ the unique optimal solution to (3.3)? Recall that the descent cone of a function $f$ at a point $\mathbf{x}_{0}$ is defined as

To control the size of $C^{o}$, first consider a single norm $\left\|\cdot\right\|_{\diamond}$, with dual norm $\left\|\cdot\right\|_{\diamond}^{*}$. Suppose that $\left\|\cdot\right\|_{\diamond}$ is $L$-Lipschitz: $\left\|\mathbf{x}\right\|_{\diamond}\leq L\left\|\mathbf{x}\right\|_{2}$ for all $\mathbf{x}$. Then $\left\|\mathbf{x}\right\|_{2}\leq L\left\|\mathbf{x}\right\|_{\diamond}^{*}$ for all $\mathbf{x}$ as well. Noting that

for any $\mathbf{v}\in\partial\left\|\cdot\right\|_{\diamond}(\mathbf{x}_{0})$, we have

A more geometric way of summarizing this is as follows: for $\mathbf{x}\neq\mathbf{0}$, let

and denote the circular cone with axis $\mathbf{x}$ and angle $\theta$. Then if $\mathbf{x}_{0}\neq\mathbf{0}$, and $\theta=\cos^{-1}(\left\|\mathbf{x}_{0}\right\|_{\diamond}/L\left\|\mathbf{x}_{0}\right\|_{2})$,

For $f=\sum_{i}\lambda_{i}\left\|\cdot\right\|_{(i)}$, notice that every element of $\partial f(\mathbf{x}_{0})$ is a conic combination of elements of the $\partial\left\|\cdot\right\|_{(i)}(\mathbf{x}_{0})$. Since each of the $\partial\left\|\cdot\right\|_{(i)}(\mathbf{x}_{0})$ is contained in a circular cone with axis $\mathbf{x}_{0}$, $\partial f(\mathbf{x}_{0})$ is also contained in a circular cone:

Suppose that $\left\|\cdot\right\|_{(i)}$ is $L_{i}$-Lipschitz. For $\mathbf{x}_{0}\neq\mathbf{0}$, set $\theta_{i}=\cos^{-1}\left(\left\|\mathbf{x}_{0}\right\|_{(i)}/L\left\|\mathbf{x}_{0}\right\|_{2}\right)$. Then

So, the subdifferential of our combined regularizer $f$ is contained in a circular cone whose angle is given by the largest of the $\theta_{i}$.

How does this behavior affect the recoverability of $\mathbf{x}_{0}$ via (3.3)? The informal reasoning above suggests that as $\theta$ becomes smaller, the descent cone $\mathcal{C}$ becomes larger, and we require more measurements to recover $\mathbf{x}_{0}$. This can be made precise using an elegant framework introduced by Amelunxen et. al. [ALMT13]. They define the statistical dimension of the convex cone $\mathcal{C}$ to be the expected norm of the projection of a standard Gaussian vector onto $C$:

Using tools from spherical integral geometry, [ALMT13] shows that for linear inverse problems with Gaussian measurements, a sharp phase transition in recoverability occurs around $m=\delta(\mathcal{C})$. We will need only one side of their result; for more details see [ALMT13]. We state a slight variant here:

To apply this result to our problem, we lower bound the statistical dimension $\delta(\mathcal{C})$, of the descent cone $\mathcal{C}$ of $f$ at $\mathbf{x}_{0}$. Using the Pythagorean theorem, monotonicity of $\delta(\cdot)$, and Lemma 4, we calculate

Moreover, using the properties of statistical dimension, we are able to prove an upper bound for the statistical dimension of circular cone, which improves the constant in existing results [ALMT13, McC13].

Finally, by combining (3.11) and Lemma 5, we have $\delta(C)\geq n\min_{i}\cos^{2}\theta_{i}-2$. Using Corollary 4, we obtain:

Let $\mathbf{x}_{0}\neq\mathbf{0}$. Suppose that for each $i$, $\left\|\cdot\right\|_{(i)}$ is $L_{i}$-Lipschitz. Set

and $\kappa=\min_{i}\kappa_{i}$. Then if $m\leq\kappa-2$,

Thus, for reliable recovery, the number of measurements needs to be at least proportional to $\kappa$.E.g., if $m=(\kappa-2)/2$, the probability of success is at most $4\exp(-(\kappa-2)/64)$. Notice that $\kappa=\min_{i}\kappa_{i}$ is determined by only the best of the structures. Per Table 1, $\kappa_{i}$ is often on the order of the number of degrees of freedom in a generic object of the $i$-th structure. For example, for a $k$-sparse vector whose nonzeros are all of the same magnitude, $\kappa=k$.

Theorem 5 together with Table 1 leads us to the phenomenon that recently discovered by Oymak et. al. [OJF+12]: for recovering objects with multiple structures, a combination of structure-inducing norms tends to be not significantly more powerful than the best individual structure-inducing norm. As we demonstrate, this general behavior follows a clear geometric interpretation that the subdifferential of a norm at $\mathbf{x}_{0}$ is contained in a relatively small circular cone with central axis $\mathbf{x}_{0}$.

We can specialize Theorem 5 to low-rank tensors as follows: if ${\boldsymbol{\mathcal{X}}}$ is a $K$-mode $n\times n\times\dots\times n$ tensor of Tucker rank $(r,r,\dots,r)$, then for each $i$, $\left\|{\boldsymbol{\mathcal{X}}}\right\|_{(i)}\doteq\left\|{\boldsymbol{\mathcal{X}}}_{(i)}\right\|_{*}$ is $L=\sqrt{n}$-Lipschitz. Hence,

A Better Convexification: Square Norm

The number of measurements promised by Corollary 2 and Theorem 3 is actually the same (up to constants) as the number of measurements required to recover a tensor ${\boldsymbol{\mathcal{X}}}_{0}$ which is low-rank along just one mode. Since matrix nuclear norm minimization correctly recovers a $n_{1}\times n_{2}$ matrix of rank $r$ when $m\geq Cr(n_{1}+n_{2})$ [CRPW12], solving

also exactly recovers ${\boldsymbol{\mathcal{X}}}_{0}$ with high probability when $m\geq Crn^{K-1}$.

This suggests a more mundane explanation for the difficulty with (3.2): the term $rn^{K-1}$ comes from the need to reconstruct the right singular vectors of the $n\times n^{K-1}$ matrix ${\boldsymbol{\mathcal{X}}}_{(1)}$. If we had some way of matricizing a tensor that produced a more balanced (square) matrix and also preserved the low-rank property, we could substantially reduce this effect, and reduce the overall sampling requirement. In fact, this is possible when the order $K$ of ${\boldsymbol{\mathcal{X}}}_{0}$ is four or larger.

We can view ${\boldsymbol{\mathcal{X}}}_{[j]}$ as a natural generalization of the standard tensor matricization. When $j=1$, ${\boldsymbol{\mathcal{X}}}_{[j]}$ is nothing but ${\boldsymbol{\mathcal{X}}}_{(1)}$. However, when some $j>1$ is selected, ${\boldsymbol{\mathcal{X}}}_{[j]}$ becomes a more balanced matrix. This reshaping also preserves some of the algebraic structures of ${\boldsymbol{\mathcal{X}}}$. In particular, we will see that if ${\boldsymbol{\mathcal{X}}}$ is a low-rank tensor (in either the CP or Tucker sense), ${\boldsymbol{\mathcal{X}}}_{[j]}$ will be a low-rank matrix.

(1) If ${\boldsymbol{\mathcal{X}}}$ has CP decomposition ${\boldsymbol{\mathcal{X}}}=\sum_{i=1}^{r}\lambda_{i}\mathbf{a}_{i}^{(1)}\circ\mathbf{a}_{i}^{(2)}\circ\cdots\circ\mathbf{a}_{i}^{(K)}$, then

(2) If ${\boldsymbol{\mathcal{X}}}$ has Tucker decomposition ${\boldsymbol{\mathcal{X}}}={\boldsymbol{\mathcal{C}}}\times_{1}\mathbf{U}_{1}\times_{2}\mathbf{U}_{2}\times_{3}\cdots\times_{K}\mathbf{U}_{K}$, then

Thus, $\mathbf{\mathcal{X}}_{[j]}$ is not only more balanced but also maintains the low-rank property of tensor $\mathbf{\mathcal{X}}$. In the following, we show how this new matricization can lead to better relaxations for tensor recovery. For ease of discussion, we assume $\mathbf{\mathcal{X}}$ has the same length (say $n$) along each mode and has Tucker rank $(r,r,\cdots,r)$. We write $\mathbf{\mathcal{X}}_{\square}\doteq\mathbf{\mathcal{X}}_{[\lfloor\frac{K}{2}\rfloor]}$ and call $\left\|{\boldsymbol{\mathcal{X}}}\right\|_{\square}:=\left\|\mathbf{\mathcal{X}}_{\square}\right\|_{\star}$ the square norm of tensor ${\boldsymbol{\mathcal{X}}}$. Since $\mathbf{\mathcal{X}}_{\square}$ is low-rank, we can attempt to recover ${\boldsymbol{\mathcal{X}}}$ by solving

Using Lemma 7 and Proposition 3.11 of [CRPW12], we can prove that this relaxation exactly recovers ${\boldsymbol{\mathcal{X}}}_{0}$, when the number of measurements is sufficienly large:

(1) If ${{\mathbf{\mathcal{X}}}_{0}}$ has CP rank $r$, using (4.4), $m\geq Crn^{\lceil\frac{K}{2}\rceil}$ is sufficient to recover ${{\mathbf{\mathcal{X}}}_{0}}$ with high probability. (2) If ${{\mathbf{\mathcal{X}}}_{0}}$ has Tucker rank $(r,r,\cdots,r)$, using (4.4), $m\geq Cr^{\lfloor\frac{K}{2}\rfloor}n^{\lceil\frac{K}{2}\rceil}$ is sufficient to recover ${{\mathbf{\mathcal{X}}}_{0}}$ with high probability.

Compared with $\Omega(rn^{K-1})$ measurements required by the sum-of-nuclear-norms model, the sample complexity, $O(r^{\lfloor\frac{K}{2}\rfloor}n^{\lceil\frac{K}{2}\rceil})$, required by the square reshaping (4.4), is always within a constant of it, much better for small $r$ and $K\geq 4$ – e.g., by a multiplicative factor of $n^{\lfloor K/2\rfloor-1}$ when $r$ is a constant. This is a significant improvement. However, there are also two clear limitations. First, no improvement is obtained for the case $K=3$. Second, the improved sample complexity in Theorem 6 is still suboptimal compared to the nonconvex model (2.1).

It is also worth noting that for tensors with different lengths or ranks, Theorem 3 and Theorem 6 can be easily modified. It remains true that for a large class of tensors, our square reshaping is capable of reducing the number generic measurements required by SNN model. However, the comparison between sum-of-nuclear-norms and square norm becomes quite subtle then. Concrete instances can be definitely constructed so that square norm model does not have any advantage over the SNN model even for $K>3$ (e.g. a tensor of size $1000\times 10\times 10\times 10$ with Tucker rank $(1,1,1,1)$). On the other hand, our square norm model can sometimes be blessed by unbalanced tensors. For example, consider a tensor of size $4\times 9\times 12\times 3$ with Tucker rank $(2,2,1,1)$. Then our reshaping matrix is a $36\times 36$ square matrix with rank $1$, which is a matrix with very good (perfect) conditions.

Simulation Results for Tensor Completion

Tensor completion attempts to reconstruct the low-rank tensor ${\boldsymbol{\mathcal{X}}}_{0}$ based on observations over a subset of its entries $\Omega$. By imposing appropriate incoherence conditions (and modifying slightly arguments in [Gro11]), it is possible to prove recovery guarantees for each of the following programs:

Unlike the recovery problem under Gaussian random measurements, due to the lack of sharp upper bounds, we have no proof that our square norm formulation outperforms the SNN model here. However, our simulation results below strongly suggest that (5.2) also performs much better than (5.1) for tensor completion case.

Conclusion

In this paper, we establish several theoretical bounds for the problem of low-rank tensor recovery using random Gaussian measurements. For the nonconvex model (2.1), we show that \big{(}(2r)^{K}+2nrK+1\big{)} measurements are sufficient to recover any ${\boldsymbol{\mathcal{X}}}_{0}\in\mathfrak{T}_{r}$ almost surely. We highlight that though the nonconvex recovery program is NP-hard in general, it does serve a baseline for evaluating tractable (convex) approaches. For the conventional convex surrogate sum-of-nuclear-norms (SNN) model (3.2), we prove a necessary condition that $\Omega(rn^{K-1})$ Gaussian measurements are required for reliable recovery. This lower bound is derived from our study on multi-structured object recovery under a very general setting, which can be applied to many scenarios. To narrow the apparent gap between the non-convex model and the SNN model, we unfold the tensor into a more balanced matrix while preserving its low-rank property, leading to our square-norm model (4.4). We prove that $O(r^{\lfloor\frac{K}{2}\rfloor}n^{\lceil\frac{K}{2}\rceil})$ measurements are sufficient to recover a tensor ${\boldsymbol{\mathcal{X}}}_{0}\in\mathfrak{T}_{r}$ with high probability. Though the theoretical results only pertain to Gaussian measurements, our simulation result for tensor completion also suggests that square-norm model outperforms the SNN model.

Compared with $\Omega(rn^{K-1})$ measurements required by the sum-of-nuclear-norms model, the sample complexity, $O(r^{\lfloor\frac{K}{2}\rfloor}n^{\lceil\frac{K}{2}\rceil})$, required by the square reshaping (4.4), is always within a constant of it, much better for small $r$ and $K\geq 4$. Although this is a significant improvement, compared with the nonconvex model (2.1), the improved sample complexity achieved by square norm model is however still suboptimal. It remails an open problem to obtain near-optimal convex relaxations for all $K>2$.

More broadly speaking, to recover objects with multiple structures, regularizing with a combination of individual structure-inducing norms is proven to be substantially suboptimal (Theorem 5 and also [OJF+12]). The resulting sample requirements tend to be much larger than the intrinsic degrees of freedom of the low-dimensional manifold that the structured signal lies in. Our square-norm model for the low-rank tensor recovery demonstrates the possibility that a better exploitation in those structures can significantly reduce this sample complexity. However, there are still no clear clues on how to intelligently utilize several simultaneous structures generally, and moreover how to design tractable method to recover multi-structured objects with near minimal number of measurements. These problems are definitely worth pursuing in future study and we hope that our work may also inspire researchers working in many other multi-structured recovery problems.

Acknowledgment

It is a great pleasure to acknowledge conversations with Michael McCoy (Caltech), Ju Sun (Columbia), Han-wen Kuo (Columbia), Martin Lotz (Manchester), Zhiwei Qin (WalmartLabs). JW was supported by Columbia University startup funding and Office of Naval Research award N00014-13-1-0492.

References

Appendix A Proofs for Section 2

The arguments we used below are primarily adapted from [ENP11], where their interest is to establish the number of Gaussian measurements required to recover a low rank matrix by rank minimization.

Notice that every ${\boldsymbol{\mathcal{D}}}\in\mathfrak{S}_{2r}$, and every $i$, $\left\langle{\boldsymbol{\mathcal{G}}}_{i},{\boldsymbol{\mathcal{D}}}\right\rangle$ is a standard Gaussian random variable, and so

Let $\mathfrak{N}$ be an $\varepsilon$-net for $\mathfrak{S}_{2r}$ in terms of $\left\|\cdot\right\|_{F}$. Because the measurements are independent, for any fixed $\bar{{\boldsymbol{\mathcal{D}}}}\in\mathfrak{S}_{2r}$,

Moreover, for any ${\boldsymbol{\mathcal{D}}}\in\mathfrak{S}_{2r}$, we have

This follows from the basic fact that for any tensor ${\boldsymbol{\mathcal{X}}}$ and matrix $\mathbf{U}$ of compatible size,

which can be established by direct calculation. Write

where the first inequality follows from triangle inequality and the second inequality follows from the fact that $\left\|{\boldsymbol{\mathcal{C}}}\right\|_{F}=1$, $\left\|\mathbf{U}_{j}\right\|=1$, $\mathbf{U}_{i}^{*}\mathbf{U}_{i}=\mathbf{I}$ and ${\mathbf{U}_{i}^{\prime}}^{*}\mathbf{U}_{i}^{\prime}=\mathbf{I}$. ∎

The idea of this proof is to construct a net for each component of the Tucker decomposition and then combine those nets to form a compound net with the desired cardinality.

Clearly $\#\mathfrak{S}_{2r}^{\prime}\leq\left(\frac{3(K+1)}{\varepsilon}\right)^{(2r)^{K}+2nrK}$. The rest is to show that $\mathfrak{S}_{2r}^{\prime}$ is indeed an $\varepsilon$-net covering $\mathfrak{S}_{2r}$ with respect to the Frobenius norm.

For any fixed ${\boldsymbol{\mathcal{D}}}=[[{\boldsymbol{\mathcal{C}}};\mathbf{U}_{1},\cdots,\mathbf{U}_{K}]]\in\mathfrak{S}_{2r}$ where ${\boldsymbol{\mathcal{C}}}\in\mathfrak{C}$ and $\mathbf{U}_{i}\in\mathcal{O}$, by our constructions above, there exist ${\boldsymbol{\mathcal{C}}}^{\prime}\in\mathfrak{C}^{\prime}$ and $\mathbf{U}_{i}^{\prime}\in\mathcal{O}^{\prime}$ such that $\left\|{\boldsymbol{\mathcal{C}}}-{\boldsymbol{\mathcal{C}}}^{\prime}\right\|_{F}\leq\frac{3(K+1)}{\varepsilon}$ and $\left\|\mathbf{U}_{i}-\mathbf{U}^{\prime}_{i}\right\|\leq\frac{3(K+1)}{\varepsilon}$. Then ${\boldsymbol{\mathcal{D}}}^{\prime}=[[{\boldsymbol{\mathcal{C}}}^{\prime};\mathbf{U}^{\prime}_{1},\cdots,\mathbf{U}^{\prime}_{K}]]\in\mathfrak{S}^{\prime}_{2r}$ is within $\varepsilon$-distance from ${\boldsymbol{\mathcal{D}}}$, since by the triangle inequality derived in Lemma 2, we have

Appendix B Proofs for Section 3

Denote $\lambda=\delta(\mathcal{C})-m$. Then following [ALMT13, Thm. 7.1], we have

Summing up the above inequalities, we have

Suppose $n$ is odd. Since the intersection of $\mbox{circ}_{n+1}(\theta)$ with any $n$-dimensional linear subspace containing $\mathbf{e}_{n+1}$ is an isometric image of $\mbox{circ}_{n}(\theta)$, by [ALMT13, Prop. 4.1], we have

Thus, taking both cases ($n$ is even and $n$ is odd) into consideration, we have

Notice that for any fixed $m>0$, the function $f:\;t\to 4\exp\left(-\frac{(t-m)^{2}}{16t}\right)$ is decreasing for $t\geq m$. Then due to Corollary 4 and the fact that $\delta(\mathcal{C})\geq\kappa-2\geq m$, we have

Appendix C Proofs for Section 4

(1) By the definition of ${\boldsymbol{\mathcal{X}}}_{[j]}$, it is sufficient to prove that the vectorization of the right hand side of (4.2) equals $\mbox{vec}({\boldsymbol{\mathcal{X}}}_{(1)})$.

Since ${\boldsymbol{\mathcal{X}}}=\sum_{i=1}^{r}\lambda_{i}\mathbf{a}_{i}^{(1)}\circ\mathbf{a}_{i}^{(2)}\circ\cdots\circ\mathbf{a}_{i}^{(K)}$, we have

where the last equality follows from the fact that $\mbox{vec}(\mathbf{a}\circ\mathbf{b})=\mathbf{b}\otimes\mathbf{a}$. Similarly, we can derive that the vectorization of the right hand side of (4.2),

Thus, equation (4.2) is valid. (2) The above argument can be easily adapted to prove the second claim. Since ${\boldsymbol{\mathcal{X}}}={\boldsymbol{\mathcal{C}}}\times_{1}\mathbf{U}_{1}\times_{2}\mathbf{U}_{2}\times_{3}\cdots\times_{K}\mathbf{U}_{K}$, we have

where the last equality follows from the fact that $\mbox{vec}(\mathbf{ABC})=(\mathbf{C}^{*}\otimes\mathbf{A})\mbox{vec}(\mathbf{B})$. Similarly, we can derive that the vectorization of the right hand side of (4.3),

Appendix D Algorithms for Section 5

In this section, we will discuss in detail our implementation of accelerated linearized Bregman algorithm for the following problem:

By introducing auxiliary variable ${\boldsymbol{\mathcal{W}}}$ and splitting ${\boldsymbol{\mathcal{X}}}$ into ${\boldsymbol{\mathcal{X}}}_{1},\;{\boldsymbol{\mathcal{X}}}_{2},\;\cdots,\;{\boldsymbol{\mathcal{X}}}_{K}$, it can be easily verified that problem (D.1) is equivalent to

whose objective function is now separable.

where we denote ${\boldsymbol{\mathcal{Y}}}_{i}$ as the dual variable for the constraint ${\boldsymbol{\mathcal{X}}}_{i}={\boldsymbol{\mathcal{W}}}$ and denote ${\boldsymbol{\mathcal{Z}}}$ as the dual variable for the last constraint $\mathcal{P}_{\Omega}[{\boldsymbol{\mathcal{W}}}]=\mathcal{P}_{\Omega}[{\boldsymbol{\mathcal{X}}}_{0}]$. Since the objective function in (D) is separable, each setup of the ALB algorithm is easy to solve as we can see from Algorithm 1 The Shrinkage operator in line 4 of Algorithm 1 performs the regular shrinkage on the singular values of the $i$th unfolding matrix of ${\boldsymbol{\mathcal{Y}}}_{i}^{k}$, i.e. $({\boldsymbol{\mathcal{Y}}}_{i}^{k})_{(i)}$, and then folds the resulting matrix back into tensor..

For our numerical experiment ($K=4$), we choose smoothing parameter $\mu=50\|\mathbf{\mathcal{X}}_{0}\|_{F}$ and step size $\tau=\frac{1}{5\mu}$. Empirically, we observe that larger values of $\mu$ do not result in a better recovery performance. This is consistent with the theoretical results established in [LY12, ZCCZ11].