Coded matrix computation: numerical stability, partial stragglers and sparse input matrices

on YouTube ↗43m

" summary

Introduces a real-valued coding scheme that embeds rotation and circulant permutation matrices so Vandermonde-like decoding matrices have unit-circle conditioning without complex arithmetic, achieving the known optimal recovery threshold while keeping worker cost low. Proposes a block-cyclic, class-based assignment that subpacketizes to exploit partial stragglers and preserves sparsity (only a small fraction of A blocks are coded), proves worst-case Q bounds and shows numerical experiments where condition numbers drop from ~10^14 to ~10^2 and decoding succeeds.

AI-written summary · about

" chapters (6)

1. 0:00Coded matrix computation intro
2. 5:08Vandermonde instability
3. 15:01Stable coded computation
4. 27:13Partial stragglers handling
5. 34:24Sparse matrices trade-offs
6. 42:10Summary

" related talks

• 25mSimple, Efficient and Neural Algorithms for Sparse CodingAnkur Moitra · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 44mStochastic Integration via Error-Correcting CodesDimitris Achlioptas · Random Instances and Phase Transitions (Simons Institute, 2016)
• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018
• 37mSparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial CouplingFlorent Krzakala · Coding: From Practice to Theory
• 26mAdaptive Coding over Countable AlphabetsStéphane Boucheron · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 45mTeaching an old code a new trickRüdiger Urbanke · Random Instances and Phase Transitions (Simons Institute, 2016)
• 31mMulti-version Coding and Shared Memory EmulationViveck Cadambe · Coding: From Practice to Theory