FoCM 2014 conference

Workshop C1 - Computational Algebraic Geometry

December 19, 15:30 ~ 15:50 - Room B12

Algorithmic and Geometric Aspects of Sparse Decomposition

Bernard Mourrain

Inria, France   -

Several problems in signal processing, tensor decomposition, sparse interpolation, polynomial optimization, etc reduce to the reconstruction of sum of exponential functions from truncated moment sequences. Prony proposed in 1795 a method to solve this problem for functions of one variable, when enough moments are known. We describe a generalization in several variables and a new algorithm to compute the decomposition of series as sums of exponential functions. An ingredient of the approach is a flat extension property, which is related to the commutation property of multiplication operators modulo a zero-dimensional ideal. We analyze this problem from a geometric point of view, describe its connection with the Hilbert scheme of points and present some applications to reconstruction and approximation problems.

View abstract PDF