Departmental Colloquium
Lihong Zhi
ICERM
Sparse Polynomial Interpolation and Symmetric Tensor Decomposition
Abstract: The sparse interpolation problem has been studied and widely used in many different areas of science and engineering since the work of Prony (1795). Ankur Moitra in his paper at STOC 2015 has given an in-
depth analysis of how oversampling improves the conditioning of the arising Prony systems for sparse interpolation and signal recovery from numeric data. Moitra assumes that oversampling is done for a number of samples beyond the actual sparsity of the polynomial/signal. We give an algorithm that can be used to compute the sparsity and estimate the minimal number of samples needed in numerical sparse interpolation. Some recent work on computing the symmetric tensor rank by Prony's method will also be introduced.
Friday October 5, 2018 at 3:00 PM in 636 SEO