The Convex Geometry of Blind Deconvolution and Matrix Completion Revisited

Explore the convex geometry of blind deconvolution and matrix completion in this 50-minute lecture by Felix Krahmer from the Hausdorff Center for Mathematics. Delve into the challenges of low-rank matrix recovery from structured measurements, focusing on matrix completion and randomized blind deconvolution problems. Examine the limitations of nuclear norm minimization and the construction of approximate dual certificates. Analyze the geometric perspective of reconstruction error bounds under adversarial noise, revealing why dimensional factors cannot be avoided in certain frameworks. Discover how these factors only arise for very small noise levels and learn about alternative approaches that offer dimension-independent constants with mild rank dependence. Cover topics such as wireless communication, coherence terms, Gaussian measurements, rank manifolds, convex singular values, and tangent spaces. Conclude with an outlook on open questions in this field of study.

Intro
Blind Deconvolution
Wireless Communication
Nuclear Norm
Assumptions
Coherence term
Dual certificates
Dimension factors
Dimensional factor
Descent codes
Gaussian measurements
Rank manifold
Convex singular values
Negative result
Descent cone
Parabola
Approximation behavior
Proof
Lower Bounds
Tangent Space
Hm Star
Matrix Completion Revisited
Outlook Open Questions