Genericity of the apocalypse phenomenon in low-rank optimization

Details

Supervisors

Olikier, Guillaume ; Absil, Pierre-Antoine

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

enLow-rank optimization aims to minimize a function over the matrices of bounded rank, a problem at the heart of data science and signal processing. A natural and inexpensive algorithm for it, known as P2GD, is prone to a subtle failure called an apocalypse: it can stall at a singular point that is not a stationary point, while its own diagnostic measure falsely signals convergence. Corrective variants such as P2GDR and PGD-P2GD repair this defect, but at a cost, and it has remained unclear whether the apocalypse is a rare accident worth tolerating or an unavoidable feature of the geometry. This thesis confronts the question on the simplest setting where the geometry can be written down explicitly, combining a systematic numerical exploration with an analysis of the continuous-time limit of P2GD, namely its gradient flow.