Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms

Introduction

Low rank tensors — similar to low rank matrices — are widely used in many applications. The rank of tensor $T$ is defined as the minimum number $m$ such that $T$ can be written as the sum of $m$ rank-1 tensors. This agrees with the definition of matrix rank. However, most of the corresponding tensor problems are much harder: for $p\geq 3$ computing the rank of the tensor (as well as many related problems) is NP-hard [Hås90, HL09]. Tensor rank is also not as well-behaved as matrix rank (see for example the survey [Com14]).

Unlike matrices, low rank tensor decompositions are often unique [Kru77], which is important in many applications. In special cases (especially when rank $m$ is less than dimension $n$) tensor decomposition can be efficiently computed. Such specialized tensor decompositions have been the key algorithmic ideas in many recent algorithms for learning latent variable models, including mixture of Gaussians, Independent Component Analysis, Hidden Markov Model and Latent Dirichlet Allocation (see [AGH+14]). In many cases tensor decomposition can be viewed as reinterpreting previous spectral learning results [Cha96, MR06, AFH+13, AHK12]. This new interpretation has also inspired many new works (e.g. [AGHK13, BCMV14, GHK15]).

A common limitation in early tensor decomposition algorithms is that they only work for the undercomplete case when rank $m$ is at most the dimension $n$. Although there are some attempts to decompose tensors in the overcomplete case ($m>n$) [DLCC07, BCMV14, ABG+13], all these works require 4-th or higher order tensors. In many machine learning applications, the number of samples required to accurately estimate a 4-th order tensor is too large. In practice algorithms based on 3rd order tensor are much more preferable. Therefore we are interested in the key question: are there any efficient algorithms for overcomplete 3rd order tensor decomposition?

In the worst case setting, overcomplete 3rd order tensors are not well-understood. Kruskal [Kru77] showed the tensor decomposition is unique when the rank $m\leq 1.5n-1$ and the components are in general position, but there is no efficient algorithm known for finding this decomposition. Constructing an explicit 3rd order tensor with rank $\Omega(n^{1+\epsilon})$ will give nontrivial circuit complexity lowerbounds [Str73], while the best known rank bound for an explicit 3rd order matrix is only $3n-O(\log n)$ [AFT11].

For many of the learning applications, it is natural to consider the average case problem where the components of the tensor are chosen according to a random distribution. In this case [AGJ14] give a polynomial time algorithm that can find the true components when $m=Cn$ for any constant $C>0$ (however the runtime depends exponentially on $C$).

This paper also considers this average case setting and gives a quasi-polynomial algorithm for decomposing the tensor when $m$ can be as large as $n^{3/2}$. The main idea of the algorithm is based on sum-of-squares (SoS) SDP hierarchy ([Par00, Las01], see Section 2 and the recent survey [BS14]). The main difficulty in handling overcomplete 3rd order tensors is that there is no natural unfolding (i.e. mapping to a matrix) that can certify the rank of the tensor. We can unfold a 4-th order tensor $T$ into a matrix $M$ of size $n^{2}\times n^{2}$ where $M_{(i_{1},i_{2}),(i_{3},i_{4})}=T_{i_{1},i_{2},i_{3},i_{4}}$. However, unfolding 3rd order tensor will result in a very unbalanced matrix of dimension $n\times n^{2}$ that cannot have rank more than $n$. Intuitively, the power of SoS-based algorithm is that it can provide higher-order “pseudo-moments” that will allow us to use nontrivial unfoldings.

In particular, the key component of the proof is a way of certifying injective norm (see Section 2) of random tensors, which is closely related to the problem of certifying the 2-to-4 norm of random matrices[BBH+12]. Recently, there has been an increasing number of applications of SoS hierarchy to learning problems. [BKS14] give algorithms for finding the sparsest vectors in a subspace, which is closely related to many learning problems. [BKS15] give a new algorithm for dictionary learning that can handle nearly linear sparsity, and also an algorithm for robust tensor decomposition.However their result requires a tensor of high order. [BM15] studies a related problem of tensor prediction, also using ideas of SoS hierarchies.

In this paper we give a quasi-polynomial time algorithm for decomposing third-order tensors when the rank $m$ is almost as large as $n^{3/2}$ and the components of the tensor is chosen randomly. More concretely, we define $\mathcal{D}_{m,n}$ to be a distribution of third order tensors of the following form:

For tensors in distribution $\mathcal{D}_{m,n}$ our algorithm can recover the decomposition as long as $m\ll n^{3/2}$.

Given a tensor $T=\sum_{i=1}^{m}a_{i}^{\otimes 3}$ sampled from distribution $\mathcal{D}_{m,n}$, when $m\ll n^{3/2}$ there is an algorithm that runs in time $n^{O(\log n)}$ and with high probability returns a decomposition $T\approx\sum_{i=1}^{m}\hat{a}_{i}^{\otimes 3}$ that is $0.1$-close to the true decomposition.

Our result easily generalizes to many other distributions for $a_{i}$ (including a uniform random vector in unit sphere or a spherical Gaussian).

The algorithm does not output a very accurate solution (the accuracy can be improved to $\epsilon$ with an exponential dependency on $1/\epsilon$). However it is known that alternating minimization algorithms can refine the decomposition once we have a nice initial point[AGJ14]:

Given a tensor $T$ from distribution $\mathcal{D}_{m,n}$ ($m\ll n^{3/2}$), and an initial solution that is $0.1$-close to the true decomposition, then for any $\epsilon>0$ (that may depend on $n$) there is an algorithm that runs in time $\operatorname{poly}(n,\log 1/\epsilon)$ that with high probability finds a refined decomposition that is $\epsilon$-close to the true decomposition.

Combining the two results we have an algorithm that runs in time $n^{O(\log n)}\operatorname{poly}\log(1/\epsilon)$ that recovers a decomposition that is component-wise $\epsilon$-close to the true decomposition.

Given a tensor $T=\sum_{i=1}^{m}a_{i}^{\otimes 3}$ sampled from distribution $\mathcal{D}_{m,n}$, when $m\ll n^{3/2}$ for any $\epsilon>0$ there is an algorithm that runs in time $n^{O((\log n))}\operatorname{poly}\log(1/\epsilon)$ and with high probability returns a decomposition $T\approx\sum_{i=1}^{m}\hat{a}_{i}^{\otimes 3}$ that is $\epsilon$-close to the true decomposition.

The main idea in proving Theorem 1.1 is the observation that when the tensor is generated randomly from $\mathcal{D}_{m,n}$, the true components are close to the maximizers of the multilinear form $T(x,x,x)=\sum_{i,j,k\in[n]}T_{i,j,k}x_{i}x_{j}x_{k}=\sum_{i=1}^{m}\langle a_{i},x\rangle^{3}$. The maximum value of $T(x,x,x)$ on unit vectors $\|x\|=1$ is known as the injective norm of the tensor. Computing or even approximating the injective norm is known to be hard [Gur03, HM13]. A key component of our approach is a sum-of-square algorithm (see Section 2 for preliminaries about sum-of-square algorithms) that certifies that the injective norm of a random tensor from $\mathcal{D}_{m,n}$ is small.

For a tensor $T$ in distribution $\mathcal{D}_{m,n}$, when $m\ll n^{3/2}$ with high probability the injective norm of $T$ is bounded by $1+o(1)$. Further, this can be certified in polynomial time.

The rest of this paper is organized as follows: In Section 2 we introduce tensor notations and SoS hierarchies. Then we describe the main idea of the proof which relates tensor decomposition to the injective norm of tensor (Section 3). In Section 4 we give a polynomial time algorithm for certifying the injective norm of a random 3rd order tensor. Using this as a key tool in Section 5 we present the quasi-polynomial time algorithm that can decompose randomly generated tensors when $m\ll n^{3/2}$.

Preliminaries

Tensors

There is a bijection between 3rd order symmetric tensors and homogeneous degree 3 polynomials. In particular, for a tensor $T$ we define its corresponding polynomial $T(x,x,x)=\sum_{i,j,k=1}^{n}T_{i,j,k}x_{i}x_{j}x_{k}$. It is easy to verify that if $T=\sum_{i=1}^{m}a_{i}^{\otimes 3}$ then $T(x,x,x)=\sum_{i=1}^{m}\langle a_{i},x\rangle^{3}$.

The injective norm $\|T\|_{inj}$ is defined to be the maximum value of the corresponding polynomial on the unit sphere, that is:

It is not hard to prove when $m\ll n^{3/2}$, and the tensor $T$ is chosen from the distribution $\mathcal{D}_{m,n}$, with high probability $1-o(1)\leq\|T\|_{inj}\leq 1+o(1)$, and in fact the value $T(x,x,x)$ is only close to $1$ if $x$ is close to one of the components $a_{i}$. We will give a (SoS) proof of this fact in Section 5

Sum-of-Square Algorithms and Proofs

Here we will only briefly introduce the notations and key concepts that are used in this paper, for more detailed discussions and references about SoS proofs we refer readers to [BS14] (especially Section 2).

Sum-of-squares proof system is a proof system for polynomial equalities and inequalities. Given a set of constraints $\{r_{i}(x)=0\}$, and a degree bound $d$, we say there is a degree $d$ SoS proof for $p(x)\geq q(x)$ if $p(x)-q(x)$ can be written as a sum of squares of polynomials modulo $r_{i}(x)=0$, as defined formally below.

For a set of constraints $R=\{r_{1}(x)=0,\dots,r_{t}(x)=0\}$, and an integer $d$, we write

Note that the constraints set can be easily generalized to a set of inequalities by adding auxiliary variables. For example, constraint $r(x)\geq 0$ can be implemented as $r(x)=z^{2}$ where $z$ is an auxiliary variable.

Many well-known inequalities can be proved using a low degree SoS proof, among them the most useful and important one is Cauchy-Schwarz inequality, which can be proved via degree-2 sum of squares. Another one is that $x^{T}Ax\preceq\|A\|\|x\|^{2}$. This is pretty useful when $A$ is a random matrix where we can use random matrix theory to bound the spectral norm of $A$.

In order to turn an SoS arguments into an algorithm, we often consider the pseudo-expectation. Just as we have expectations for real distributions, we think of pseudo-expectation as expectations for pseudo-distributions that cannot be distinguished from true expectations using low degree polynomials. Pseudo-expectation can be viewed as a dual of SoS refutations.

The relationship between pseudo-expectations and SoS refutations can be summarized in the following informal lemma:

For a set of constraints $R$, either there is an SoS refutation of degree $d$ that refutes $R$, or there is a degree $d$ pseudo-expectation that satisfies $R$. Such a refutation/pseudo-expectation can be found in $\operatorname{poly}(tn^{d})$ time.

Relating Tensor Decompositions and Injective Norm

In this section we introduce the main idea of our proof. Given a tensor $T=\sum_{i=1}^{m}a_{i}^{\otimes 3}$ from distribution $\mathcal{D}_{m,n}$, we first make some observations about its corresponding polynomial $T(x,x,x)=\sum_{i=1}^{m}\langle a_{i},x\rangle^{3}$.

When $x=a_{1}$, we know $T(a_{1},a_{1},a_{1})=1+\sum_{i=2}^{m}\langle a_{i},a_{1}\rangle^{3}$. Here conditioned on $a_{1}$, the second term is a sum of independent random variables ($\langle a_{i},a_{1}\rangle^{3}$). By the distribution $\mathcal{D}_{m,n}$ we know these variables have mean 0 and absolute value around $1/n^{3/2}$. Standard concentration bounds show when $m\ll n^{3/2}$ with high probability $T(a_{1},a_{1},a_{1})=1\pm o(1)$.

On the other hand, suppose $x$ is a random vector in the unit sphere, then $T(x,x,x)=\sum_{i=1}^{m}\langle a_{i},x\rangle^{3}$ is again a sum of random variables. By concentration bounds we know for any particular $x$, when $m\ll n^{3/2}$ with high probability $T(x,x,x)=o(1)$. This can actually be generalized to all vectors $x$ that do not have large correlation with $a_{i}$’s using $\epsilon$-net arguments.

For a random tensor $T\sim\mathcal{D}_{m,n}$, when $m=n^{3/2}$ with high probability $T(x,x,x)\leq 1+o(1)$ for $\|x\|=1$. Further when $T(x,x,x)$ is close to $1$ the vector $x$ is close to one of the components $a_{i}$’s.

Later we will give a SoS proof for this observation. Based on this observation, if we want to find a component, then it suffices to find a vector $x$ such that $T(x,x,x)$ is close to $1$. Using the idea of pseudo-expectations, we can do this in two steps:

Certifying Injective Norm

In this section, we give Algorithm 1 based on SoS hierarchy that certifies the injective norm of random tensor. In particular, we will prove Theorem 1.3 which we restate in more details here.

For random tensor $T$, we hope to show that with high probability, the tensor norm is less than $1+1/\log n$ can be proved via SoS.

With high probability over the randomness of the tensor $T$, for $r(x)=\|x\|^{2}-1$,

That is, when $m\ll n^{3/2}$, the objective value of the convex program in Algorithm 1 is less than $1+1/\log n$ with high probability for random tensor.

Now we need to prove Theorem 4.2. We first use Cauchy-Schwarz inequality to transform LHS of (3) to a degree-4 polynomial, which would then correspond to 4th order tensors and enable non-trivial unfoldings.

This is a direct application of Cauchy-Schwarz inequality:

Expanding this quantity, and using the fact that $\|a_{i}\|=1$, we get

With high probability over the randomness of $a_{i}$’s,

The harder part of the proof is to deal with the second term $p(x)$ on the RHS of (4). The naive idea would be to let $y=x^{\otimes 2}$ and view $p(x)$ as a degree-2 polynomial of $y$,

Here $N$ is an $n^{2}$ by $n^{2}$ random matrix that depends on $a_{i}$’s. Suppose $N$ has spectral norm less than $o(1)$, then we have $y^{T}Ny\preceq\|N\|\|y\|^{2}$, and by replacing $y=x\otimes x$ we obtain $p(x)=q(x\otimes x)\preceq o(1)$. However, in our case the matrix $N$ have spectral norm much larger than $o(1)$.

Our key insight is that we could have different ways to unfold $p(x)$ into a degree-2 polynomial. In particular, we use the following way of unfolding:

where $M$ is the $n^{2}$ by $n^{2}$ matrix that encodes the coefficients of $q^{\prime}(y)$,

It turns out that $q^{\prime}(y)$ still have the property that $q^{\prime}(x\otimes x)=p(x)$. The matrix $M$ has much better spectral norm bound, which leads us to the bound for $p(x)$.

When $m\ll n^{3/2}$, the matrix $M=\sum_{i\neq j}\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$ has spectral norm at most $\widetilde{O}(m/n^{3/2})$ and as a direct consequence,

First we give an informal and suboptimal bound for intuition. Let $B$ be the $n^{2}\times m^{2}$ matrix whose $(i,j)$-column $(i,j\in[m])$ is $a_{i}\otimes a_{j}$ (viewed as an $n^{2}$ dimensional vector). Then $M$ can be written as $M=B\operatorname{diag}(\langle a_{i},a_{j}\rangle)_{i\neq j}B^{T}$. Note that $B$ can also be written as $A\otimes A$ where $\otimes$ is the Kronecker product of two matrices, so we have $\|B\|=\|A\|^{2}\lesssim m/n$. Then we can bound the norm of $M$ by $\|M\|\leq\|B\|\|\operatorname{diag}(b)\|\|B\|\leq(m/n)\cdot\max_{i,j}|\langle a_{i},a_{j}\rangle|\cdot(m/n)\lesssim m^{2}/n^{5/2}$, where we used the incoherence of $a_{i}$’s, that is, $|\langle a_{i},a_{j}\rangle|\lesssim 1/\sqrt{n}$. This will only be $o(1)$ when $m\lesssim n^{1.25}$.

Intuitively, this proof is not tight because we ignored potential cancellation caused by the randomness of $\langle a_{i},a_{j}\rangle$. Note that $\langle a_{i},a_{j}\rangle$ have expectation 0, but we treated them all as positive $1/\sqrt{n}$. If we assume that $\langle a_{i},a_{j}\rangle$’s are independent $\pm 1/\sqrt{n}$, then $M=\sum_{i\neq j}\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$ would be a sum of PSD matrices with random weights and we can apply more standard matrix concentration bounds to make sure cancellations happen.

However, $\langle a_{i},a_{j}\rangle$ are of course not independent and our key idea is to decouple the randomness of $\langle a_{i},a_{j}\rangle$.

(Sketch) We first replace the vectors $a_{i}$’s with $\sigma_{i}a_{i}$ where $\sigma_{i}$ is a random $\pm 1$ variable. This is OK because the distribution of $a_{i}$ and $\sigma_{i}a_{i}$ are the same. Now we first sample the $a_{i}$’s, conditioned on the samples $M=\sum_{i\neq j}\sigma_{i}\sigma_{j}\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$ (where only $\sigma_{i}$’s are still random). Now since the vectors $a_{i}$’s are all fixed, the correlation between different terms only depends on scalar variables $\sigma_{i}\sigma_{j}$, and we never use the term $\sigma_{i}^{2}$ (because $i\neq j$).

By a result of [PMS95], in this case we can decouple the product $\sigma_{i}\sigma_{j}$. In particular, in order to prove concentration properties for $M$, it suffices to prove concentration for a different matrix $\sum_{i\neq j}\sigma_{i}\tau_{j}\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$. Here $\tau\in\{\pm 1\}^{m}$ is an independent copy of $\sigma_{i}$’s. In this way we have decoupled the randomness in $\sigma_{i}$ and $\tau_{i}$, and the rest of the Lemma can follow from careful matrix concentration analysis. ∎

We give the full proof of Lemma 3 in Appendix A.2.

Quasi-polynomial Time Algorithm for Tensor Decomposition

In this section we give a quasi-polynomial time algorithm for decomposing random 3rd order tensors in distribution $\mathcal{D}_{m,n}$. In particular, we prove Theorem 1.1 which we restate with more details below:

A key component of our algorithm is a way of sampling pseudo-distributions given in [BKS15]:

The main intuition is to use Cauchy-Schwarz and Hölder inequalities (like what we used in Claim 1) to raise the power in the sum $\sum_{i=1}^{m}\langle a_{i},x\rangle^{d}$ (we start with $d=3$ and hope to get to $d=k$). When the degree is high enough we can afford to do an averaging argument and lose a factor of $m$ to go from the sum to a individual vector, because $e^{-\epsilon k}=\operatorname{poly}(m)$. The detailed proof is given in Appendix B.1.

(sketch) We prove Theorem 5.1 by induction. Suppose $s$ already contains a set of vectors $\hat{a}_{i}$’s, where for each $\hat{a}_{i}$ there is a corresponding $a_{j}$ that satisfies $\|\hat{a}_{i}-a_{j}\|\leq 0.1$. We would like to show with high probability in the next iteration, the algorithm finds a new component that is different from all the previously found $a_{i}$’s.

In order to do that, we need to show the following:

The SDP in Step 3 of Algorithm 2 is feasible and gives a valid pseudo-expectation.

For any valid pseudo-expectation, with high probability we get an unit vector $c$ that satisfies $T(c,c,c)\geq 0.99$, and $c$ is far from all the previously found $a_{i}$’s.

For any unit vector $c$ such that $T(c,c,c)\geq 0.99$, there must be a component $a_{i}$ such that $\|a_{i}-c\|\leq 0.1$.

The details in this proof can be found in Appendix B.2.

Conclusion

In this paper we give the first algorithm that can decompose an overcomplete 3rd order tensor when the rank $m$ is almost $n^{3/2}$ that matches the $n^{p/2}$ bounds for even order tensors. Our argument is based on a special unfolding of the tensor and a decoupling argument for matrix concentration. We feel such techniques can be useful in other settings.

Tensor decompositions are widely applied in machine learning for learning latent variable models. Although the SoS based algorithm have poor dependency on the accuracy $\epsilon$, in the case of tensor decomposition we can actually use SoS as an initialization algorithm. We hope such ideas can help solving more problems in machine learning.

We thank Anima Anandkumar, Boaz Barak, Johnathan Kelner, David Steurer, Venkatesan Guruswami for helpful discussions at various stages of this work.

References

Appendix A Omitted Proofs in Section 4

With high probability over the randomness of $a_{i}$’s,

Recall [BBH+12] showed that when $m\ll n^{2}$,

Here in order to improve this bound, we consider the square of the LHS of (6) and apply Cauchy-Schwarz (similar to Claim 1),

We will bound the first term of (11) by $1+o(1)$. We simply let $y=x^{\otimes 3}$ and let $B$ be the matrix whose $i$th row is $a_{i}^{\otimes 3}$. Then $f(y)=\|By\|^{2}$ has the property that $f(x^{\otimes 3})=\sum_{i=1}^{m}\langle a_{i},x\rangle^{6}$. Therefore it suffices to prove that $f(y)\preceq(1+o(1)\|y\|^{2}$ or equivalently $\|B\|\leq 1+o(1)$.

Consider the matrix $BB^{T}$. It is a $n$ by $n$ matrix with diagonal entries 1 and off diagonal entries of the form $\langle a_{i}^{\otimes 3},a_{j}^{\otimes 3}\rangle=\langle a_{i},a_{j}\rangle^{3}$. By the incoherence of $a_{i}$’s, we have $\langle a_{i},a_{j}\rangle^{3}\lesssim 1/n^{3/2}$. Then by Gershgorin disk theorem, we have $\|BB^{T}\|\leq 1+\widetilde{O}(m/n^{3/2})=1+\delta$. It follows that $\|B\|\leq 1+\widetilde{O}(m/n^{3/2})$. Therefore,

For the second term of (11), we apply Cauchy-Schwarz again:

Note that the matrix $A=[a_{1}|\dots|a_{m}]$ has spectral norm bound $\|A\|\lesssim\sqrt{m/n}$, and therefore

Then using Equation 10, and the equation above, we have

Then by 13 and 14 and Lemma 13, we have that

Hence, combining equation (15), (12) and (11) we have that

Using Lemma 13 again, we complete the proof of Lemma 6.

A.2 Proof of Lemma 3

When $m\ll n^{3/2}$, the matrix $M=\sum_{i\neq j}\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$ has spectral norm at most $\widetilde{O}(m/n^{3/2})$ and as a direct consequence,

As suggested in the proof sketch, we first use a simple symmetrization which allows us to focus on the randomness of signs of $\langle a_{i},a_{j}\rangle$. For simplicity of notation, let $Q_{ij}:=\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j})^{T}$. Let $\sigma\in\{\pm 1\}^{m}$ be uniform random $\pm 1$ vector and define $M^{\prime}$ as

We claim that $M^{\prime}$ has the same distribution as $M$, since $a_{i}$ has the same distribution as $\sigma_{i}a_{i}$. Then from now on we condition on the event that $a_{i}$’s have incoherence property and low spectral norm, that is, $\langle a_{i},a_{j}\rangle\lesssim 1/\sqrt{n}$, $\|A\|=\left\|[a_{1}|a_{2}\dots|a_{m}]\right\|\lesssim\sqrt{m/n}$, and we will only focus on the randomness of $\sigma$. Ideally we want to write $M^{\prime}$ as a sum of independent random matrices so that we can apply matrix Bernstein inequality. However, now the random coefficients are $\sigma_{i}\sigma_{j}$, and they are not independent with each other.

A key observation here is that the sum is only over the indices $(i,j)$ with $i\neq j$, therefore we can use Theorem 1 of [PMS95] (restated as Theorem C.1 in the end) to decouple the correlation first.

Theorem C.1 basically says that to study the concentration of a sum of the form $\sum_{i\neq j}f_{ij}(X_{i},X_{j})$, it is up to constant factor similar to the concentration of the sum $\sum_{i\neq j}f_{ij}(X_{i},Y_{j})$ where $Y_{i}$ is an independent copy of $X_{i}$. Applying the theorem to our situation, we have that there exists absolute constant $C$ such that

and $\sigma,\tau$ are independently uniform over $\{-1,+1\}^{m}$.

Now it suffices to bound the norm of $M^{\prime\prime}$. We proceed by rewriting $M^{\prime\prime}$ as

We study the properties of $T_{i}$ first.

Recall that $Q_{ij}=\langle a_{i},a_{j}\rangle(a_{i}\otimes a_{j})(a_{i}\otimes a_{j}^{T})$. In the definition 18 of $T_{i}$, the index $i$ is fixed and we take sum over $j$. Therefore it will be convenient to write $Q_{ij}$ as $Q_{ij}=\langle a_{i},a_{j}\rangle(a_{i}a_{i}^{T})\otimes(a_{j}a_{j})^{T}$ where $\otimes$ is the Kronecker product between matrices. Then $T_{i}$ can be written as

We apply the Matrix Bernstein inequality (Theorem C.2) on the right factor. Matrix Bernstein bound requires spectral norm bound for individual matrices, and a variance bound.

For the spectral norm of individual matrices, we check that $\|\tau_{j}\langle a_{i},a_{j}\rangle a_{j}a_{j}^{T}\|\lesssim 1/\sqrt{n}$ (by incoherence). For variance we know

where we used the spectral norm of $A$ and the fact that $\langle a_{i},a_{j}\rangle^{2}\lesssim 1/n$.

Therefore by Matrix Bernstein’s inequality (Theorem C.2) we have that whp, over the randomness of $\tau$,

Using the fact that for two matrices $P$ and $Q$, if $P\preceq Q$ and $R$ is PSD, then $R\otimes P\preceq R\otimes Q$ (see Claim 3), it follows that

Finally we use union bound and conclude with high probability this is true for any $i$. ∎

Using (17), we get that whp, $\|M^{\prime}\|\leq\widetilde{O}(m/n^{3/2})$. Since $M^{\prime}$ and $M$ has the same distribution, we conclude that whp, $\|M\|\leq\widetilde{O}(m/n^{3/2})$. ∎

We complete the proof by providing the following claim about Kronecker products.

If $P\preceq Q$ and $R$ is psd, then $R\otimes P\preceq R\otimes Q$.

Therefore $R\otimes P\preceq R\otimes Q$. ∎

A.3 Main Theorem for Certifying Injective Norm

Appendix B Omitted Proof in Section 5

First we will show that for a valid pseudo-expectation, the sum of $\langle a_{i},x\rangle^{4}$ and $\langle a_{i},x\rangle^{6}$ are also bounded. This actually follows directly from the proof of Lemma 2 and 3.

for $\epsilon=\widetilde{O}(m/n^{3/2})+O(\tau)$.

For proving the lower bounds in (20), we first pseudo-expectation on equation 15, we have that

Then taking pseudo-expectation over equation (16), we obtain that

Note that by equation (22) and Cauchy-Schwarz, we have

Combining the two equations above, we obtain that

By equation (2.5) of [BKS15], we the following SoS version of Holder inequality. For any integer $t,d$ and $k=t(d-2)$,

Let $v_{i}=\langle a_{i},x\rangle^{2}$, we have

By Lemma 2, we have that with high probability over randomness of $a_{i}$’s, $\sum_{i=1}^{m}\langle a_{i},x\rangle^{4}\preceq 1+\widetilde{O}(m/n^{3/2})$, and it follows that

By picking $d=3$, we have $t=k$. Taking $t=O(\log m/\epsilon)$ and combining equation (23) and (24), we have that

Applying pseudo-expectation on both hands, we obtain,

Note that by Cauchy-Schwarz and equation (20), we have

Combining the two equations above, we obtain that for $\delta=\widetilde{O}(m/n^{3/2})$,

Therefore by averaging argument, there exists $i$ such that

Lemma 4 follows directly from the two lemmas above.

B.2 Proof of Theorem 5.1

In this section we prove the main theorem in Section 5.

We first prove that with high probability $T(a_{i},a_{i},a_{i})\geq 1-1/\log n$ for all $i$. This is easy because $T(a_{i},a_{i},a_{i})=1+\sum_{j\neq i}\langle a_{i},a_{j}\rangle^{3}$. Conditioned on $a_{i}$, the values $\langle a_{i},a_{j}\rangle$ are sub-Gaussian random variables with mean 0 and variance $1/n$, so by standard concentration bounds we know with high probability $\sum_{j\neq i}\langle a_{i},a_{j}\rangle^{3}\geq-1/\log n$. We can then take the union bound and conclude $T(a_{i},a_{i},a_{i})\geq 1-1/\log n$ for all $i$.

For any valid pseudo-expectation in Step 3, with high probability we get an unit vector $c$ that satisfies $T(c,c,c)\geq 0.99$, and $c$ is far from all the previously found $a_{i}$’s.

Taking pseudo-expectations over both sides, we have that

where we’ve used the constraint $\langle s_{i},x\rangle^{2}\leq 1/8$ and induction hypothesis $\|s_{i}-a_{i}\|\leq 0.1$.

Now applying Theorem 5.2 we get a vector $c$ that is has inner-product $1-O(\epsilon)$ with $a_{i}$. Therefore $T(c,c,c)=T(a_{i},a_{i},a_{i})+T(c-a_{i},a_{i},a_{i})+T(c,c-a_{i},a_{i})+T(c,c,a_{i})\geq 1-1/\log n-3\|T\|_{\textrm{inj}}\|c-a_{i}\|\geq 0.99$. Here $T(x,y,z)=\sum_{i_{1},i_{2},i_{3}}T_{i_{1},i_{2},i_{3}}x_{i_{1}}y_{i_{2}}z_{i_{3}}$ is the multilinear form for the tensor, and note that this step of the proof does not need to be SoS because we already have the vector $c$ from Theorem 5.2. ∎

For any unit vector $c$ such that $T(c,c,c)\geq 0.99$, there must be a component $a_{i}$ such that $\|a_{i}-c\|\leq 0.1$.

Finally, the runtime of Line 3 in Algorithm 2 is $n^{O(k)}$, and the run-time of line 4 is also $n^{O(k)}$. Therefore the total runtime is $n^{O(k)}$.

Appendix C Matrix Concentrations

In this section we introduce theorems used to prove matrix concentrations. First we need the following lemma for decoupling the randomness in the sum.

Let $X_{1},\dots,X_{n}$, $Y_{1},\dots,Y_{n}$ are independent random variables on a measurable space over $S$, where $X_{i}$ and $Y_{i}$ has the same distribution for $i=1,\dots,n$. Let $f_{ij}(\cdot,\cdot)$ be a family of functions taking $S\times S$ to a Banach space $(B,\|\cdot\|)$. Then there exists absolute constant $C$, such that for all $n\geq 2$, $t>0$,

We also need the Matrix Bernstein’s Inequality:

Consider a finite sequence $\{X_{k}\}$ of independent, random symmetric matrices with dimension $d$. Assume that each random matrix satisfies

Appendix D Sum-of-Square Proofs

In this section we state some lemmas that can be proved by low-degree SoS proofs. Most of these lemmas can be found in [BS14] and [BKS14] but we still give the proofs here for completeness.

[SoS proof for Cauchy-Schwarz] Cauchy-Schwarz inequality can be proved by degree-2 sum of squares proofs,

For any vector $x$, $y$, we have that for even number $k$,

Note that it suffices to prove it for one dimensional vector $x,y$. We prove by induction. For $k=2$, it just follows Cauchy-Schwarz. Suppose it is true for $k-2$ case, we have

Combing the two equations above we obtain the desired result. ∎

Suppose $M$ is $m\times n$ matrix with spectral norm $\|M\|$, then

Assume $m\leq n$ without loss of generality, and suppose $M$ has singular decomposition $M=U\Sigma V^{T}$ where $\Sigma=\operatorname{diag}(\sigma_{1},\dots,\sigma_{m})$. Let $z=x^{T}U$ and $w=V^{T}y$. Then

For a nonnegative real number $a$ and a set of polynomial $R$ and positive integer $k$, if a polynomial $p(x)$ satisfy $p(x)\preceq_{R,k}a^{2}$, then $p(x)\preceq_{R,k^{\prime}}a$ for $k^{\prime}=\max\{k,2\deg(p)\}$.

By a simple manipulation of algebra, we have that