How to Decompose a Tensor with Group Structure
- URL: http://arxiv.org/abs/2106.02680v1
- Date: Fri, 4 Jun 2021 19:27:24 GMT
- Title: How to Decompose a Tensor with Group Structure
- Authors: Allen Liu, Ankur Moitra
- Abstract summary: We study the orbit recovery problem, which is a natural abstraction for the problem of recovering a planted signal from noisy measurements under unknown group actions.
Our main result is a quasi-polynomial time algorithm to solve orbit recovery over $SO(3)$ - i.e. the cryo-electron tomography problem.
- Score: 25.313563663123354
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we study the orbit recovery problem, which is a natural
abstraction for the problem of recovering a planted signal from noisy
measurements under unknown group actions. Many important inverse problems in
statistics, engineering and the sciences fit into this framework. Prior work
has studied cases when the group is discrete and/or abelian. However
fundamentally new techniques are needed in order to handle more complex group
actions.
Our main result is a quasi-polynomial time algorithm to solve orbit recovery
over $SO(3)$ - i.e. the cryo-electron tomography problem which asks to recover
the three-dimensional structure of a molecule from noisy measurements of
randomly rotated copies of it. We analyze a variant of the frequency marching
heuristic in the framework of smoothed analysis. Our approach exploits the
layered structure of the invariant polynomials, and simultaneously yields a new
class of tensor decomposition algorithms that work in settings when the tensor
is not low-rank but rather where the factors are algebraically related to each
other by a group action.
Related papers
- Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
We show that PCA becomes computationally hard at a critical value of the signal's magnitude.
We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree.
It also lets us analyze a new problem of distinguishing between different ensembles.
arXiv Detail & Related papers (2024-04-29T14:33:24Z) - Decomposition of linear tensor transformations [0.0]
The aim of this paper is to develop a mathematical framework for exact tensor decomposition.
In the paper three different problems will be carried out to derive.
arXiv Detail & Related papers (2023-09-14T16:14:38Z) - Deep Neural-network Prior for Orbit Recovery from Method of Moments [1.4579344926652844]
Two particular orbit recovery problems of interest in this paper are multireference alignment and single-particle cryo-EM modelling.
In order to suppress the noise, we suggest using the method of moments approach for both problems while introducing deep neural network priors.
arXiv Detail & Related papers (2023-04-28T03:19:08Z) - Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras
from First Principles [55.41644538483948]
We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset.
We use fully connected neural networks to model the transformations symmetry and the corresponding generators.
Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
arXiv Detail & Related papers (2023-01-13T16:25:25Z) - Imbalance Trouble: Revisiting Neural-Collapse Geometry [27.21274327569783]
We introduce Simplex-Encoded-Labels Interpolation (SELI) as an invariant characterization of the neural collapse phenomenon.
We prove for the UFM with cross-entropy loss and vanishing regularization.
We present experiments on synthetic and real datasets that confirm convergence to the SELI geometry.
arXiv Detail & Related papers (2022-08-10T18:10:59Z) - Unified Fourier-based Kernel and Nonlinearity Design for Equivariant
Networks on Homogeneous Spaces [52.424621227687894]
We introduce a unified framework for group equivariant networks on homogeneous spaces.
We take advantage of the sparsity of Fourier coefficients of the lifted feature fields.
We show that other methods treating features as the Fourier coefficients in the stabilizer subgroup are special cases of our activation.
arXiv Detail & Related papers (2022-06-16T17:59:01Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning.
Recent work has established lower bounds against the class of low-degree methods.
We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
We provide a completely general algorithm for solving for the equivariant layers of matrix groups.
In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before.
Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
arXiv Detail & Related papers (2021-04-19T17:21:54Z) - Symmetric Boolean Factor Analysis with Applications to InstaHide [18.143740528953142]
We show that InstaHide possesses some form of "fine-grained security" against reconstruction attacks for moderately large k.
Our algorithm, based on tensor decomposition, only requires m to be at least quasi-linear in r.
We complement this result with a quasipolynomial-time algorithm for a worst-case setting of the problem where the collection of k-sparse vectors is chosen arbitrarily.
arXiv Detail & Related papers (2021-02-02T15:52:52Z) - Disentangling by Subspace Diffusion [72.1895236605335]
We show that fully unsupervised factorization of a data manifold is possible if the true metric of the manifold is known.
Our work reduces the question of whether unsupervised metric learning is possible, providing a unifying insight into the geometric nature of representation learning.
arXiv Detail & Related papers (2020-06-23T13:33:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.