"Non UBC"@en . "DSpace"@en . "Zhi, Lihong"@en . "2017-06-04T05:00:36Z"@* . "2016-11-01T11:00"@en . "Ankur Moitra in his paper at STOC 2015 has given an in-depth analysis of how\noversampling improves the conditioning of the arising Prony systems for sparse\ninterpolation and signal recovery from numeric data. Moitra assumes that\noversampling is done for a number of samples beyond the actual sparsity of the\npolynomial/signal. We give an algorithm that can be used to compute the\nsparsity and estimate the minimal number of samples needed in numerical sparse\ninterpolation. The early termination strategy of \npolynomial interpolation\nhas been incorporated in the algorithm:\nby oversampling at a small number of\nextra sample points \nwe can diagnose\nthat the sparsity has not been reached.\n\nOur algorithm still has to make a guess, the number $\zeta$ of oversamples, and\nwe show by example that if $\zeta$ is guessed too small, premature termination\ncan occur, but our criterion is numerically more accurate\nthan that by Kaltofen, Lee and Yang\n(Proc.\ SNC 2011, ACM) \nbut not as efficiently computable. \nFor heuristic justification one has\navailable the multivariate early termination theorem by\nKaltofen and Lee\n(JSC vol.\ 36(3--4) 2003)\nfor exact arithmetic, and the numeric Schwartz-Zippel Lemma by Kaltofen,\nYang and Zhi\n(Proc.\ SNC 2007, ACM). \nA main contribution here is a modified proof of\nthe Theorem by Kaltofen and Lee that permits starting the sequence at the point\n$(1,\ldots,1)$, for scalar fields of characteristic $\ne 2$ (in characteristic~$2$\ncounter-examples are given).\n\nJoint work with Z. Hao (KLMM, Beijing) and E. Kaltofen (NC state)"@en . "https://circle.library.ubc.ca/rest/handle/2429/61827?expand=metadata"@en . "38 minutes"@en . "video/mp4"@en . ""@en . "Author affiliation: AMSS Beijing China"@en . "10.14288/1.0348078"@en . "eng"@en . "Unreviewed"@en . "Vancouver : University of British Columbia Library"@en . "Banff International Research Station for Mathematical Innovation and Discovery"@en . "Attribution-NonCommercial-NoDerivatives 4.0 International"@en . "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en . "Faculty"@en . "BIRS Workshop Lecture Videos (Oaxaca de Ju\u00E1rez (Mexico))"@en . "Mathematics"@en . "Approximations and expansions"@en . "Commutative rings and algebras"@en . "Classical analysis"@en . "Numerical sparsity determination and early termination"@en . "Moving Image"@en . "http://hdl.handle.net/2429/61827"@en .