Short-Flat Decompositions and Faster Algorithms for Linear Inverse Problems

Explore a 29-minute lecture on short-flat decompositions and their applications in solving undercomplete linear inverse problems. Delve into Kevin Tian's survey of algorithmic applications, focusing on sparse recovery and low-rank matrix completion. Discover novel principled approaches for designing iterative methods to solve these problems and their robust generalizations. Learn about the extension of the sparse recovery algorithm to solve undercomplete sparse linear systems in RIP design matrices, perturbed by a semi-random adversary, in nearly-linear time. Examine the improved noise tolerance achieved in matrix completion algorithms compared to previous state-of-the-art methods. Gain insights from recent research presented at COLT 2023 and FOCS 2023, conducted in collaboration with Jonathan A. Kelner, Jerry Li, Allen Liu, and Aaron Sidford.

Short-Flat Decompositions and Faster Algorithms for Linear Inverse Problems