Sparse interpolation in the presence of noise and outlier errors

Title: Sparse interpolation in the presence of noise and outlier errors
Speaker: Erich L.Kaltofen (Professor，ACM Fellow),  North Carolina State University
报告时间：11月2日（周五）上午9:00-10：30

报告地点：数学馆西113室

Abstract:
Blahut's 1975 decoding algorithm for Reed-Solomon error correcting codes and
Zippel's 1979 and Ben-Or/Tiwari's 1984 exact multivariate sparse interpolation
algorithms have led to numeric interpolation algorithms that require only a
number of interpolation points that is proportional to the unknown sparsity.
The algorithms are randomized, and the random distribution of the condition
numbers arising in the linear algebra substeps has been first analyzed by
Giesbrecht, Labahn and Lee in 2003.  In 2007 we have contributed, jointly with
Zhengfeng Yang and Lihong Zhi, a numeric version of Zippel's algorithm applied
to sparse rational function recovery.

Sparse model recovery has applications in medical signal processing and
compressive sensing.  Such approximate models can be reconstructed even when
the interpolation points have outlier errors.  In 2012 we have begun, jointly
with Brice Boyer, Matthew Comer, and Clement Pernet, to study numeric error
correction in sparse interpolation.

In my talk I will give an overview of all those algorithms with emphasis to
numerical algorithms and applications.

作者简介：

Erich Kaltofen received both his M.S. degree in Computer Science in

1979 and his Ph.D. degree in Computer Science in 1982 from Rensselaer

Polytechnic Institute.  He was an Assistant Professor of Computer

Science at the University of Toronto and an Assistant, Associate, and

full Professor at Rensselaer Polytechnic Institute.  Since 1996 he is

a Professor of Mathematics at North Carolina State University.  He has

held visiting positions at Tektronix in 1985, the Mathematical

Sciences Research Institute in Berkeley in 1985 and 2000, the

University of Toronto in 1991, the Ecole Normale Superieure in Lyon in

2005 and the Massachusetts Institute of Technology in 2006.

Kaltofen's current interests in the symbolic computation discipline

are hybrid symbolic/numeric algorithms, efficient algorithms

for linear and polynomial algebra, algebraic complexity theory,

and generic programming techniques for algorithm implementation.

He is a founding member of the LinBox project.

Kaltofen was the Chair of ACM's Special Interest Group on Symbolic &

Algebraic Manipulation 1993 - 95.  He serves as associate editor on

several journals on symbolic computation.  From 1985 - 87 he held an

IBM Faculty Development Award.  From 1990 - 91 he was an ACM National

Lecturer. In 2009 Kaltofen was selected an ACM Fellow.

He has edited 4 books, including the Computer Algebra Handbook in

2002, published over 140 research articles, and has developed symbolic

computation software in Lisp and C++ and contributed to commercial

symbolic computation software.  According to Microsoft Academic

Search, Kaltofen is a top-ranked author.