Sums of vectors with binary coefficients enjoy a rich history, having been studied in a myriad of different contexts ranging from probability to additive number theory. This thesis focuses on the potential of these weighted binary sums to serve as approximations for other points in d-dimensional Euclidean space. An immediate application of this topic is to quantization error analysis for finite dimensional signals and it is through this lens that we formulate the questions we address. Ideally, we would like to be able to classify how well such sums can approximate other points based on the structure of the vectors. This turns out to be an intricate question and as small perturbations in these vectors can have drastic effects on the answer.
In one dimension, the problem amounts to understanding the lengths of intervals produced by neighboring weighted binary sums. This interpretation allows us to find an exact expression for the worst error that will be encountered when using these sums to approximate, referred to as the global error. However, we find that global error is only part of the story and, for many choices of vectors, we can approximate with much greater accuracy locally. We investigate the local error behavior for several settings. In particular, we utilize the notion of discrepancy to find local results for the case where the vectors are chosen to be piecewise constant.
In dimension 2 or greater, the error analysis becomes more complicated. Our results in several dimensions are based on the assumption that the vectors form a unit norm tight frame for the ambient space. In particular, we use a probabilistic model to establish a nontrivial lower bound for the local error and investigate in more detail the specific case of the two-dimensional tight frame created by the nth roots of unity.
|Commitee:||Chatterjee, Sourav, Deift, Percy, Kohn, Robert, Nguyen, Truong-Thao|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 72/10, Dissertation Abstracts International|
|Keywords:||Approximation, Binary, Error analysis, Quantization, Quantized sums|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be