- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Numerical sparsity determination and early termination
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Numerical sparsity determination and early termination Zhi, Lihong
Description
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. The early termination strategy of polynomial interpolation has been incorporated in the algorithm: by oversampling at a small number of extra sample points we can diagnose that the sparsity has not been reached. Our algorithm still has to make a guess, the number $\zeta$ of oversamples, and we show by example that if $\zeta$ is guessed too small, premature termination can occur, but our criterion is numerically more accurate than that by Kaltofen, Lee and Yang (Proc.\ SNC 2011, ACM) but not as efficiently computable. For heuristic justification one has available the multivariate early termination theorem by Kaltofen and Lee (JSC vol.\ 36(3--4) 2003) for exact arithmetic, and the numeric Schwartz-Zippel Lemma by Kaltofen, Yang and Zhi (Proc.\ SNC 2007, ACM). A main contribution here is a modified proof of the Theorem by Kaltofen and Lee that permits starting the sequence at the point $(1,\ldots,1)$, for scalar fields of characteristic $\ne 2$ (in characteristic~$2$ counter-examples are given). Joint work with Z. Hao (KLMM, Beijing) and E. Kaltofen (NC state)
Item Metadata
Title |
Numerical sparsity determination and early termination
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2016-11-01T11:00
|
Description |
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. The early termination strategy of
polynomial interpolation
has been incorporated in the algorithm:
by oversampling at a small number of
extra sample points
we can diagnose
that the sparsity has not been reached.
Our algorithm still has to make a guess, the number $\zeta$ of oversamples, and
we show by example that if $\zeta$ is guessed too small, premature termination
can occur, but our criterion is numerically more accurate
than that by Kaltofen, Lee and Yang
(Proc.\ SNC 2011, ACM)
but not as efficiently computable.
For heuristic justification one has
available the multivariate early termination theorem by
Kaltofen and Lee
(JSC vol.\ 36(3--4) 2003)
for exact arithmetic, and the numeric Schwartz-Zippel Lemma by Kaltofen,
Yang and Zhi
(Proc.\ SNC 2007, ACM).
A main contribution here is a modified proof of
the Theorem by Kaltofen and Lee that permits starting the sequence at the point
$(1,\ldots,1)$, for scalar fields of characteristic $\ne 2$ (in characteristic~$2$
counter-examples are given).
Joint work with Z. Hao (KLMM, Beijing) and E. Kaltofen (NC state)
|
Extent |
38 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: AMSS Beijing China
|
Series | |
Date Available |
2017-06-04
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0348078
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International