A Spectral Algorithm for Latent Dirichlet Allocation

Topic modeling is a generalization of clustering that posits that observations (words in a document) are generated by multiple latent factors (topics), as opposed to just one. The increased representational power comes at the cost of a more challenging unsupervised learning problem for estimating the topic-word distributions when only words are observed, and the topics are hidden. This work provides a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of multi-view models and topic models, including latent Dirichlet allocation (LDA). For LDA, the procedure correctly recovers both the topic-word distributions and the parameters of the Dirichlet prior over the topic mixtures, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method is based on an efficiently computable orthogonal tensor decomposition of low-order moments.

• Publication year

  2012

• Venue

  Algorithmica

• Publication date

  2012-04-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-014-9909-1arXiv 1204.6703
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Contrastive Learning Using Spectral Methods

  2013cited by this paper
• Tensor decompositions for learning latent variable models

  2012influential reference
• Two SVDs Suffice: Spectral decompositions for probabilistic topic modeling and latent Dirichlet allocation

  2012influential reference
• Learning Topic Models -- Going beyond SVD

  2012influential reference
• Probabilistic topic models

  2012cited by this paper
• A Method of Moments for Mixture Models and Hidden Markov Models

  2012influential reference
• Distributed Gibbs sampling for latent variable models

  2012cited by this paper
• Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders

  2012influential reference
• Learning mixtures of spherical gaussians: moment methods and spectral decompositions

  2012influential reference
• Spectral Methods for Learning Multivariate Latent Tree Structure

  2011cited by this paper
• Settling the Polynomial Learnability of Mixtures of Gaussians

  2010cited by this paper
• Online Learning for Latent Dirichlet Allocation

  2010cited by this paper
• Efficiently learning mixtures of two Gaussians

  2010cited by this paper
• Learning Mixtures of Two Gaussians

  2010cited by this paper
• Handbook of Blind Source Separation: Independent Component Analysis and Applications

  2010influential reference
• Polynomial Learning of Distribution Families

  2010cited by this paper
• Latent Dirichlet Allocation

  2009influential reference
• Tensor Decompositions and Applications

  2009cited by this paper
• Multi-view clustering via canonical correlation analysis

  2009influential reference
• Learning Mixtures of Product Distributions Using Correlations and Independence

  2008cited by this paper
• A spectral algorithm for learning Hidden Markov Models

  2008cited by this paper
• Isotropic PCA and Affine-Invariant Clustering

  2008cited by this paper
• A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

  2007cited by this paper
• Two-view feature generation model for semi-supervised learning

  2007cited by this paper
• Multi-view Regression Via Canonical Correlation Analysis

  2007cited by this paper
• Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures

  2006cited by this paper
• LEARNING MIXTURES OF SEPARATED NONSPHERICAL GAUSSIANS

  2005cited by this paper
• Learning nonsingular phylogenies and hidden Markov models

  2005influential reference
• Independent Component Analysis

  2005cited by this paper
• On Spectral Learning of Mixtures of Distributions

  2005cited by this paper
• The Spectral Method for General Mixture Models

  2005cited by this paper
• GaP: a factor model for discrete data

  2004influential reference
• A spectral algorithm for learning mixture models

  2004cited by this paper
• An elementary proof of a theorem of Johnson and Lindenstrauss

  2003cited by this paper
• Blind separation of sources, Part I" An adaptive algorithm based on neuromimetic architecture

  2002cited by this paper
• A spectral algorithm for learning mixtures of distributions

  2002cited by this paper
• Learning mixtures of arbitrary gaussians

  2001cited by this paper
• A Two-Round Variant of EM for Gaussian Mixtures

  2000cited by this paper
• Learning mixtures of Gaussians

  1999cited by this paper
• Probabilistic Latent Semantic Analysis

  1999cited by this paper
• Learning the parts of objects by non-negative matrix factorization

  1999cited by this paper
• Latent semantic indexing: a probabilistic analysis

  1998cited by this paper
• Independent component analysis, a survey of some algebraic methods

  1996influential reference
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.

  1996influential reference
• Learning linear transformations

  1996cited by this paper
• Numerical Methods for Simultaneous Diagonalization

  1993cited by this paper
• A Decomposition for Three-Way Arrays

  1993cited by this paper
• Multivariate Normal Mixtures: A Fast Consistent Method of Moments

  1993cited by this paper
• Matrix Perturbation Theory

  1991influential reference
• Moment Matrices: Applications in Mixtures

  1989cited by this paper
• Mixture densities, maximum likelihood, and the EM algorithm

  1984cited by this paper
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

  1977cited by this paper
• Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-model factor analysis

  1970influential reference
• Approximation by Sequences of Padé Approximants in Regions of Meromorphy

  1966cited by this paper
• Some mathematical notes on three-mode factor analysis

  1966cited by this paper
• The most predictable criterion.

  1935cited by this paper
• Multiple Invariants and Generalized Rank of a P‐Way Matrix or Tensor

  1928cited by this paper
• The Expression of a Tensor or a Polyadic as a Sum of Products

  1927cited by this paper
• AND T

  year unknowninfluential reference
• III. Contributions to the mathematical theory of evolution

  year unknowncited by this paper

• Public attitudes toward DeepSeek on Chinese social media: a study based on sentiment analysis and topic modeling

  2026cites this paper
• Evolution of Orthodontic Anchorage Techniques: A Comparative Analysis Using the Latent Dirichlet Allocation Algorithm

  2025cites this paper
• E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time

  2025cites this paper
• Conceptualizing visitors’ experience in heritage hotels using big data

  2024cites this paper
• Textual Factors: A Scalable, Interpretable, and Data-Driven Approach to Analyzing Unstructured Information

  2024cites this paper
• Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

  2024cites this paper
• Sustainable development and strategic management - what is on the horizon in our non-ergodic world research?

  2024cites this paper
• A Review: Comprehensive study on societal Analysis for health care system Using topic modeling Paradigms

  2024cites this paper
• A randomized algorithm for simultaneously diagonalizing symmetric matrices by congruence

  2024influential citation
• Finding a Taxi With Illegal Driver Substitution Activity via Behavior Modelings

  2024cites this paper
• Performance Analysis of Deep Learning Algorithms in Diagnosis of Malaria Disease

  2023cites this paper
• The Identification of Discrete Mixture Models

  2023cites this paper
• A Bibliometric Analysis to Identify Research Trends in Intervention Programs for Smartphone Addiction

  2023cites this paper
• A Comparison of Latent Semantic Analysis and Latent Dirichlet Allocation in Educational Measurement

  2023cites this paper
• Random Separating Hyperplane Theorem and Learning Polytopes

  2023cites this paper
• Tensor Completion via Tensor Train Based Low‐Rank Quotient Geometry Under a Preconditioned Metric

  2022cites this paper
• Efficient Bayesian estimation and use of cut posterior in semiparametric hidden Markov models

  2022cites this paper
• Designing of Latent Dirichlet Allocation Based Prediction Model to Detect Midlife Crisis of Losing Jobs due to Prolonged Lockdown for COVID-19

  2022cites this paper
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials

  2022cites this paper
• Randomized Joint Diagonalization of Symmetric Matrices

  2022influential citation
• Polynomial-Time Power-Sum Decomposition of Polynomials

  2022cites this paper
• Fast algorithm for overcomplete order-3 tensor decomposition

  2022cites this paper
• Understanding The Robustness of Self-supervised Learning Through Topic Modeling

  2022influential citation
• Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision

  2022cites this paper
• Random Tensor Theory for Tensor Decomposition

  2022cites this paper
• One Objective for All Models - Self-supervised Learning for Topic Models

  2022cites this paper
• Mixed membership Gaussians

  2022cites this paper
• Semantic similarity measure for topic modeling using latent Dirichlet allocation and collapsed Gibbs sampling

  2022cites this paper
• Understanding Document Thematic Structure

  2022cites this paper
• On-the-fly Rectification for Robust Large-Vocabulary Topic Inference

  2021cites this paper
• A Tensor-EM Method for Large-Scale Latent Class Analysis with Binary Responses

  2021cites this paper
• Method of Moments for Topic Models with Mixed Discrete and Continuous Features

  2021cites this paper
• Likelihood estimation of sparse topic distributions in topic models and its applications to Wasserstein document distance calculations

  2021cites this paper
• Measuring and Modeling Group Dynamics in Open-Source Software Development: A Tensor Decomposition Approach

  2021cites this paper
• A moment-matching metric for latent variable generative models

  2021cites this paper
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules

  2021cites this paper
• Dimension-Grouped Mixed Membership Models for Multivariate Categorical Data

  2021cites this paper
• Learning Topic Models: Identifiability and Finite-Sample Analysis

  2021influential citation
• A Tensor-EM Method for Large-Scale Latent Class Analysis with Clustering Consistency

  2021influential citation
• Decentralization and recentralization of Korean curriculum documents 2012–2017: a novel approach to text mining in curriculum studies

  2021cites this paper
• Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over $SO(3)$

  2021cites this paper
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions

  2021cites this paper
• Assigning topics to documents by successive projections

  2021cites this paper
• Author Clustering and Topic Estimation for Short Texts

  2021cites this paper
• Tensor Decompositions

  2021cites this paper
• Approximate minimization of weighted tree automata

  2020cites this paper
• Making Method of Moments Great Again? -- How can GANs learn distributions

  2020cites this paper
• A NEW FRAMEWORK FOR TENSOR PCA BASED ON TRACE INVARIANTS

  2020cites this paper
• Source Identification for Mixtures of Product Distributions

  2020influential citation
• Poisson reduced-rank models with an application to political text data

  2020cites this paper
• Visitors' experience at Angkor Wat, Cambodia: evidence from sentiment and topic analysis

  2020cites this paper
• Prior-aware Composition Inference for Spectral Topic Models

  2020cites this paper
• The Sparse Hausdorff Moment Problem, with Application to Topic Models

  2020cites this paper
• Thesis Proposal

  2020cites this paper
• When can Wasserstein GANs minimize Wasserstein Distance?

  2020influential citation
• Near-optimal sample complexity bounds for learning Latent k-polytopes and applications to Ad-Mixtures

  2020cites this paper
• Detecting approximate replicate components of a high-dimensional random vector with latent structure

  2020cites this paper
• Optimal estimation of sparse topic models

  2020cites this paper
• The popularity of eating broadcast: Content analysis of “mukbang” YouTube videos, media coverage, and the health impact of “mukbang” on public

  2020cites this paper
• Endmember Extraction From Hyperspectral Imagery Based on Probabilistic Tensor Moments

  2020cites this paper
• Deconvolution of dust mixtures.

  2020cites this paper
• Making Method of Moments Great Again? -- How can GANs learn the target distribution

  2020cites this paper
• Latent Dirichlet Analysis of Categorical Survey Responses

  2019cites this paper
• The Application of Symmetric Tensor Decomposition to Parameter Estimation of Latent Variable Models

  2019cites this paper
• Applications of Stochastic Gradient Descent to Nonnegative Matrix Factorization

  2019cites this paper
• Textual Factors and Finance Applications ∗

  2019cites this paper
• Structured Bayesian Latent Factor Models with Meta-data

  2019cites this paper
• Finding a latent k-polytope in O(k . nnz(data)) time via Subset Smoothing.

  2019cites this paper
• Predicting Returns with Text Data

  2019cites this paper
• Uniform attribute‐content model

  2019cites this paper
• Prior Specification for Bayesian Matrix Factorization via Prior Predictive Matching

  2019cites this paper
• Practical Correlated Topic Modeling and Analysis via the Rectified Anchor Word Algorithm

  2019influential citation
• Topic Modeling via Full Dependence Mixtures

  2019cites this paper
• Learning Networked Exponential Families with Network Lasso

  2019cites this paper
• Learning Nonlinear Mixtures: Identifiability and Algorithm

  2019cites this paper
• Learning latent variable models: efficient algorithms and applications

  2019influential citation
• Text Mining with Constrained Tensor Decomposition

  2019cites this paper
• A Spectral Method for Off-Policy Evaluation in Contextual Bandits under Distribution Shift

  2019cites this paper
• Dirichlet Simplex Nest and Geometric Inference

  2019cites this paper
• Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing

  2019cites this paper
• Minimum Volume Topic Modeling

  2019cites this paper
• The latent topic block model for the co-clustering of textual interaction data

  2019influential citation
• Anchor-Free Correlated Topic Modeling

  2019cites this paper
• Decision Making With Heterogeneous Agents: Elicitation, Aggregation, and Causal Effects

  2019cites this paper
• Weighted Tensor Completion for Time-Series Causal Inference

  2019cites this paper
• Urban Functional Area Division Based on Cell Tower Classification

  2019cites this paper
• A general method for regularizing tensor decomposition methods via pseudo-data

  2019influential citation
• Spectral Learning on Matrices and Tensors

  2019cites this paper
• Large Scale Cloud Deployment of Spectral Topic Modeling

  2019cites this paper
• A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics

  2018cites this paper
• Robust moment estimation and improved clustering via sum of squares

  2018cites this paper
• Joint-Stochastic Spectral Inference for Robust Co-occurence Modeling and Latent Topic Analysis

  2018influential citation
• Spectral Inference Networks: Unifying Spectral Methods With Deep Learning

  2018cites this paper
• A new method of moments for latent variable models

  2018cites this paper
• Algorithmic Aspects of Machine Learning

  2018influential citation
• SpectralLeader: Online Spectral Learning for Single Topic Models

  2018influential citation
• Simulation for AI

  2018cites this paper
• An end-to-end Differentially Private Latent Dirichlet Allocation Using a Spectral Algorithm

  2018influential citation
• Guaranteed Simultaneous Asymmetric Tensor Decomposition via Orthogonalized Alternating Least Squares

  2018influential citation
• L G ] 6 F eb 2 01 8 Recovering Structured Probability Matrices

  2018cites this paper