Matrix Completion for the Independence Model

on YouTube ↗25m

" summary

Given observed entries first use 2×2 minors to fill entries and collapse connected blocks into single entries by summing them the partial matrix is completable to a nonnegative rank one probability matrix exactly when the sum over blocks of the square roots of block sums satisfies sum of square roots ≤ 1 equality gives uniqueness while strict inequality gives an (n−2)-dimensional family of completions for n>2 An explicit irreducible polynomial cuts out the boundary (degree 2^{n−1} in the matrix case)

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:25Main problem
3. 1:20Motivation
4. 3:132 x 2 diagonal matrices
5. 5:12Diagonal partial matrices
6. 8:31Example: General partial matrices
7. 13:38Semialgebraic sets
8. 15:383 x 3 diagonal matrices
9. 16:49Completion algorithm for two blocks
10. 17:37Completion algorithm for more blocks
11. 19:332 x 2 x 2 tensors

" related talks

• 37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?Rachel Ward · Optimization, Statistics and Uncertainty
• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)
• 47mCausal Matrix Completion: Applications to Offline Causal Reinforcement LearningAnish Agarwal · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 01h 00mOn Approximating the Covering Radius and Finding Dense Lattice SubspacesDaniel Dadush · Lattices: Geometry, Algorithms and Hardness 2020
• 29mCausal Matrix CompletionAnish Agarwal · Algorithmic Aspects of Causal Inference 2022
• 34mMatrix Martingales in Randomized Numerical Linear AlgebraRasmus Kyng · Randomized Numerical Linear Algebra and Applications 2018
• 47mUniqueness of Tensor Decomposition and Identifiability in Mixture ModelsAditya Bhaskara · Tensors in Computer Science and Geometry 2014
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)