Spectral methods from tensor networks

DOI10.1145/3313276.3316357MaRDI QIDQ5212833zbMATH OpenOpenAlexFDO

Authors Ankur Moitra, Alexander S. Wein

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

multi-reference alignmentorbit recoveryspectral methodstensor networks

Mathematics Subject Classification ID

Vector and tensor algebra, theory of invariants (15A72) Factor analysis and principal components; correspondence analysis (62H25) Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms (68W40)

Abstract: A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problems (such as tensor decomposition and tensor PCA), although they are not presented this way, can be viewed as spectral methods on matrices built from simple tensor networks. In this work we leverage the full power of this abstraction to design new algorithms for certain continuous tensor decomposition problems. An important and challenging family of tensor problems comes from orbit recovery, a class of inference problems involving group actions (inspired by applications such as cryo-electron microscopy). Orbit recovery problems over finite groups can often be solved via standard tensor methods. However, for infinite groups, no general algorithms are known. We give a new spectral algorithm based on tensor networks for one such problem: continuous multi-reference alignment over the infinite group SO(2). Our algorithm extends to the more general heterogeneous case.

Recommendations

• Spectral algorithms for tensor completion
• Tensor networks in machine learning
• Spectral algorithms
• Orthogonal decomposition of tensor trains
• A spectral theory for tensors

Cited in

(11)

• Noisy tensor completion via the sum-of-squares hierarchy
• Spectral methods for matrices and tensors
• The tensor network theory library
• Tensor Network Skeletonization
• Spectrum Cartography via Coupled Block-Term Tensor Decomposition
• Tensor networks in machine learning
• Estimation under group actions: recovering orbits from invariants
• Average-case complexity of tensor decomposition for low-degree polynomials
• Deep neural-network prior for orbit recovery from method of moments
• Adaptive spectral community detection in temporal networks: a modularity optimization framework with memory and smoothing
• Fourier analysis of iterative algorithms

This page was built for publication: Spectral methods from tensor networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212833)