Recovering structured probability matrices
From MaRDI portal
Abstract: We consider the problem of accurately recovering a matrix B of size M by M , which represents a probability distribution over M2 outcomes, given access to an observed matrix of "counts" generated by taking independent samples from the distribution B. How can structural properties of the underlying matrix B be leveraged to yield computationally efficient and information theoretically optimal reconstruction algorithms? When can accurate reconstruction be accomplished in the sparse data regime? This basic problem lies at the core of a number of questions that are currently being considered by different communities, including building recommendation systems and collaborative filtering in the sparse data regime, community detection in sparse random graphs, learning structured models such as topic models or hidden Markov models, and the efforts from the natural language processing community to compute "word embeddings". Our results apply to the setting where B has a low rank structure. For this setting, we propose an efficient algorithm that accurately recovers the underlying M by M matrix using Theta(M) samples. This result easily translates to Theta(M) sample algorithms for learning topic models and learning hidden Markov Models. These linear sample complexities are optimal, up to constant factors, in an extremely strong sense: even testing basic properties of the underlying matrix (such as whether it has rank 1 or 2) requires Omega(M) samples. We provide an even stronger lower bound where distinguishing whether a sequence of observations were drawn from the uniform distribution over M observations versus being generated by an HMM with two hidden states requires Omega(M) observations. This precludes sublinear-sample hypothesis tests for basic properties, such as identity or uniformity, as well as sublinear sample estimators for quantities such as the entropy rate of HMMs.
Recommendations
Cites work
- 10.1162/jmlr.2003.3.4-5.993
- A spectral algorithm for learning hidden Markov models
- A spectral algorithm for learning mixture models
- An automatic inequality prover and instance optimal identity testing
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection thresholds and the weak Ramanujan property
- Computing a nonnegative matrix factorization -- provably
- Concentration and regularization of random graphs
- Efficiently learning mixtures of two Gaussians
- Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
- Estimating a density under order restrictions: Nonasymptotic minimax risk
- Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
- Exact Recovery in the Stochastic Block Model
- Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
- Latent semantic indexing: A probabilistic analysis
- Learning mixtures of Gaussians in high dimensions
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Matrix Completion From a Few Entries
- Minimax rates of community detection in stochastic block models
- On testing expansion in bounded-degree graphs
- Optimal algorithms for testing closeness of discrete distributions
- Polynomial Learning of Distribution Families
- Smoothed analysis of tensor decompositions
- Spectral redemption in clustering sparse networks
- Spectral techniques applied to sparse random graphs
- Streaming and sublinear approximation of entropy and information distances
- Strong lower bounds for approximating distribution support size and the distinct elements problem
- Sublinear algorithms for testing monotone and unimodal distributions
- Tensor decompositions for learning latent variable models
- Testing closeness of discrete distributions
- The Power of Linear Estimators
This page was built for publication: Recovering structured probability matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993314)
