Fourier PCA and robust tensor decomposition

DOI10.1145/2591796.2591875zbMATH Open1315.68209arXiv1306.5825OpenAlexW2080207853MaRDI QIDQ5259594FDOQ5259594

Ying Xiao, Navin Goyal, Santosh S. Vempala

Publication date: 26 June 2015

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

Abstract: Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution.We make this method algorithmic by developing a tensor decomposition method for a pair of tensors sharing the same vectors in rank-$1$ decompositions. Our main application is the first provably polynomial-time algorithm for underdetermined ICA, i.e., learning an $nimesm$ matrix $A$ from observations $y=Ax$ where $x$ is drawn from an unknown product distribution with arbitrary non-Gaussian components. The number of component distributions $m$ can be arbitrarily higher than the dimension $n$ and the columns of $A$ only need to satisfy a natural and efficiently verifiable nondegeneracy condition. As a second application, we give an alternative algorithm for learning mixtures of spherical Gaussians with linearly independent means. These results also hold in the presence of Gaussian noise.

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

zbMATH Keywords

tensor decompositionsample complexityindpendent component analysis

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Multilinear algebra, tensor calculus (15A69)

Cites Work

• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (14)

• Multi-Reference Alignment in High Dimensions: Sample Complexity and Phase Transition
• Eigenvectors of Orthogonally Decomposable Functions
• On the optimization landscape of tensor decompositions
• Estimation under group actions: recovering orbits from invariants
• Smoothed analysis for tensor methods in unsupervised learning
• Robustness of the Inner–Outer Factorization and of the Spectral Factorization for FIR Data
• Robust dimension reduction, fusion frames, and Grassmannian packings
• Estimating Higher-Order Moments Using Symmetric Tensor Decomposition
• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• Kronecker-decomposable robust probabilistic tensor discriminant analysis
• Parallel active subspace decomposition for tensor robust principal component analysis
• Average-case complexity of tensor decomposition for low-degree polynomials
• The Sample Complexity of Multireference Alignment
• Overcomplete Order-3 Tensor Decomposition, Blind Deconvolution, and Gaussian Mixture Models

Uses Software

• SuLQ

This page was built for publication: Fourier PCA and robust tensor decomposition

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