Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

DOI10.1145/2746539.2746605zbMath1321.68396arXiv1407.1543OpenAlexW2053885701MaRDI QIDQ2941498

Jonathan A. Kelner, David Steurer, Boaz Barak

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1543

zbMATH Keywords

sum of squaresdictionary learningsparse coding

Mathematics Subject Classification ID

Semidefinite programming (90C22) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (23)

Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Smoothed analysis for tensor methods in unsupervised learning ⋮ On the optimization landscape of tensor decompositions ⋮ Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors ⋮ Unnamed Item ⋮ $(L_r,L_r,1)$-Decompositions, Sparse Component Analysis, and the Blind Separation of Sums of Exponentials ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Unnamed Item ⋮ Fast overcomplete dictionary construction with probabilistic guarantees ⋮ Unnamed Item ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018 ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Learning semidefinite regularizers ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ Sums of Squares and Sparse Semidefinite Programming ⋮ Convergence radius and sample complexity of ITKM algorithms for dictionary learning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compressed dictionary learning ⋮ Unnamed Item

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method