Open Collections

Page Metadata

Item Metadata

Title	Numerical sparsity determination and early termination
Creator	Zhi, Lihong
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	Mathematics Approximations and expansions Commutative rings and algebras Classical analysis
Geographic Location	Oaxaca (Mexico : State)
Type	Moving Image
FileFormat	video/mp4
Language	eng
Notes	Author affiliation: AMSS Beijing China
Series	BIRS Workshop Lecture Videos (Oaxaca (Mexico : State))
Date Available	2017-06-03
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
IsShownAt	10.14288/1.0348078
URI	http://hdl.handle.net/2429/61827
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
AggregatedSourceRepository	DSpace

Download

Media

48630-201611011100-Zhi_lrv.mp4 [ 144.96MB ]

Metadata

JSON: 48630-1.0348078.json

JSON-LD: 48630-1.0348078-ld.json

RDF/XML (Pretty): 48630-1.0348078-rdf.xml

RDF/JSON: 48630-1.0348078-rdf.json

Turtle: 48630-1.0348078-turtle.txt

N-Triples: 48630-1.0348078-rdf-ntriples.txt

Original Record: 48630-1.0348078-source.json

Citation

48630-1.0348078.ris

Cite

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.

Include Metadata Specify width in pixels (leave blank for auto-width):

                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    

Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:

http://iiif.library.ubc.ca/presentation/dsp.48630.1-0348078/manifest

Comment

Related Items