3-tensor over \({\mathbb{R}}^d\)

for example, \(\displaystyle T = \sum_{i,j,k\in [d]} T_{ijk} \cdot e_i\otimes e_j \otimes e_k\) (coordinate basis \({\left\{ e_i \right\}}_{i\in [d]}\))

unsupervised learning of sparse representations for data:

example: sparse dictionaries for natural image patches

[Mairal, Sapiro, Elad’07]

many other applications for sparse dictionaries
(e.g., reduce required amount of labeled data)

alternating minimization works well but no strong guarantees

recent alg’s with provable guarantees [Spielman-Wang-Wright’12; Agarwal-Anandkumar-Jain-Netrapalli-Tandon’14; Arora-Ge-Moitra’14]

works propose generative models (planted distributions)
common barrier for techniques: require sparsity \(\le \sqrt n\)

with SOS: [Barak-Kelner-S.’15; Ma-Shi-S.’16] only require sparsity \(\ll n\)
(based on new tensor decomposition algorithms)

concrete results: [BKS’15,MSS’16] first polynomial-time algorithms
… for overcomplete 3-tensors (under mild assumption on vectors)
… robust against spectral norm error (same order as signal)

“dream up” higher-degree moments from given moments
using sum-of-squares convex relaxations

apply classical decomposition alg’s to “dream moments” (analogous to rounding algorithm)

first attempt: find distribution \(D\) over unit vectors with matching 3rd moment and output 6th moment of \(D\)

\(\leadsto\) lifted 6th moment close to correct under mild assumptions on \({\{ a_i \}}\)

key insight: \(\mathrm{contr'n}(E,g)\) is linear matrix polynomial in Gaussian variables \(\leadsto\) great bounds for spectral norms [Oliveira;Tropp]

moments of pseudo-distr’n (will use them for matching and lifting)

key step: check \(M_{2k}(D)\succeq 0\) for \(k\le \ell\) (as \(d^k\times d^k\) matrix)

most alg’s based on convex relaxations captured by pseudo-distr’n

many classical ineq’s have SOS proofs: Cauchy–Schwarz, Hölder, …

capture properties of pseudo-distr’s (all properties by duality)

want: moment matching works even for pseudo-distributions

to show: low-degree SOS proof for above fact

will see: simple general strategy to extract fast practical algorithms from scheme with similar guarantees 🙂

approach: lift mom’s by explicit low-deg polynomial \(P\) in input tensor (choice of \(P\) informed by SOS proofs that appear in analysis)

crucial: can avoid higher tensors by exploiting tensor structure of \(P\) to “unroll” Jennrich’s algorithm

# [d,d,d]-dimensional 3-tensor
T = tf.constant(...)

# [d]-dimensional random vector
g = tf.constant(tf.random_normal([d]))

# [d,d]-dimensional random matrix
X = tf.constant(tf.random_normal([d,d]))

# iterations
for i in range(iter_num):
    X = tf.einsum('abi,cdj,ijk,k,bd->ac',T,T,T,g,X)

session.run(X)

(update \(X\) by evaluating 5-linear form in \(T\), \(T\), \(T\), \(g\), and \(X\))

first step often easier than coming up with efficient algorithm
for second step, large toolbox is emerging (reusable analyses)

unit vectors \(a_1,\ldots,a_n\in {\mathbb{R}}^d\) with
\(\max_{i\neq j} {\lvert {\langle a_i,a_j \rangle} \rvert}\le \rho\) and \(\sum_i {a_i {a_i}^\intercal} \preceq \sigma\cdot {\mathrm{Id}}\) and \(\rho \sigma^2 \le o(1)\)

proof strategy:

• find “simple regular proof” of inequality
• check that all steps are “low-deg SOS equalities”

easy to check: each inequality here is actually an equality up to sums of low-degree squares

above matrix \(M\) is explicit polynomial in \(T=\sum_i a_i^{\otimes 3}\) and \(g\) and
has \(O(d^{1+\omega})\)-time matrix-vector mult’n alg’m given \(T\) and \(g\)

\(\leadsto\) close to linear time alg. to find one \(a_i\) given \(T\)