Celebratio Mathematica

I. Daubechies, R. DeVore, C. S. Güntürk, and V. A. Vaishampayan: “Beta expansions: A new approach to digitally correct A/D conversion,” pp. 784–787 in 2002 IEEE international symposium on circuits and systems: Proceedings (Phoenix-Scottsdale, AZ, 26–29 May 2007), vol. 2. IEEE (Piscataway, NJ), 2002. incollection

We introduce a new architecture for pipelined (and also algorithmic) A/D converters that give exponentially accurate conversion using inaccurate comparators. An error analysis of a sigma-delta converter with an imperfect comparator and a constant input reveals a self-correction property that is not inherited by the successive refinement quantization algorithm that underlies both pipelined multistage A/D converters and algorithmic A/D converters. Motivated by this example, we introduce a new A/D converter, the beta converter, which has the same self-correction property as a sigma-delta converter but which exhibits higher order (exponential) accuracy with respect to the bit rate as compared to a sigma-delta converter, which exhibits only polynomial accuracy.

Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related
Vinay A. Vaishampayan	Related

I. Daubechies, R. A. DeVore, C. S. Güntürk, and V. A. Vaishampayan: “A/D conversion with imperfect quantizers,” IEEE Trans. Inform. Theory 52 : 3 (2006), pp. 874–885. MR 2238058 Zbl 1231.94036 article

This paper analyzes mathematically the effect of quantizer threshold imperfection commonly encountered in the circuit implementation of analog-to-digital (A/D) converters such as pulse code modulation (PCM) and sigma–delta (\( \Sigma\Delta \)) modulation. \( \Sigma\Delta \) modulation, which is based on coarse quantization of oversampled (redundant) samples of a signal, enjoys a type of self-correction property for quantizer threshold errors (bias) that is not shared by PCM. Although “classical” \( \Sigma\Delta \) modulation is inferior to PCM in the rate-distortion sense, this robustness feature is believed to be one of the reasons why \( \Sigma\Delta \) modulation is preferred over PCM in A/D converters with imperfect quantizers. Motivated by these facts, other encoders are constructed in this paper that use redundancy to obtain a similar self-correction property, but that achieve higher order accuracy relative to bit rate compared to classical \( \Sigma\Delta \). More precisely, two different types of encoders are introduced that exhibit exponential accuracy in the bit rate (in contrast to the polynomial-type accuracy of classical \( \Sigma\Delta \)) while possessing the self-correction property.

Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related
Vinay A. Vaishampayan	Related

I. Daubechies, R. DeVore, M. Fornasier, and S. Gunturk: “Iteratively re-weighted least squares minimization: Proof of faster than linear rate for sparse recovery,” pp. 26–29 in 2008 42nd annual conference on information sciences and systems (Princeton, NJ, 19–21 March 2008). IEEE (Piscataway, NJ), 2008. incollection

Given an \( m{\times}N \) matrix \( \Phi \), with \( m < N \), the system of equations \( \Phi x = y \) is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a “best” solution. One of the oldest is to select the one with minimal \( \ell_2 \) norm. It has been shown that in many applications a better choice is the minimal \( \ell_1 \) norm solution. This is the case in Compressive Sensing, when sparse solutions are sought.

The minimal \( \ell_1 \) norm solution can be found by using linear programming; an alternative method is Iterative Re-weighted Least Squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight \( w \), the solution with smallest \( \ell_2(w) \) norm; this weight is updated at every iteration step: if \( x^{(n)} \) is the solution at step \( n \), then \( w^{(n)} \) is defined by \[ w_i^{(n)} := \frac1{|x_i^{(n)}|},\quad i = 1,\dots,N .\]

We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix \( \Phi \) known as the Restricted Isometry Property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate \( \ell_1 \)-minimization, the exponential rate is linear; in adapted versions aimed at \( \ell_{\tau} \)-minimization with \( \tau < 1 \), we prove faster than linear rate.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

I. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntürk: “Iteratively reweighted least squares minimization for sparse recovery,” Comm. Pure Appl. Math. 63 : 1 (2010), pp. 1–38. MR 2588385 Zbl 1202.65046 ArXiv 0807.0575 article

Under certain conditions (known as the restricted isometry property, or RIP) on the \( m{\times}N \) matrix \( \Phi \) (where \( m < N \)), vectors \( x\in\mathbb{R}^N \) that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from \( y := \Phi x \) even though \( \Phi^{-1}(y) \) is typically an \( (N-m) \)-dimensional hyperplane; in addition, \( x \) is then equal to the element in \( \Phi^{-1}(y) \) of minimal \( \ell_1 \)-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining \( x \), as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector \( w \), the element in \( \Phi^{-1}(y) \) with smallest \( \ell_2(w) \)-norm. If \( x^{(n)} \) is the solution at iteration step \( n \), then the new weight \( w^{(n)} \) is defined by \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1/2} ,\] \( i = 1, \dots,N \), for a decreasing sequence of adaptively defined \( \epsilon_n \); this updated weight is then used to obtain \( x^{(n+1)} \) and the process is repeated. We prove that when \( \Phi \) satisfies the RIP conditions, the sequence \( x^{(n)} \) converges for all \( y \), regardless of whether \( \Phi^{-1}(y) \) contains a sparse vector. If there is a sparse vector in \( \Phi^{-1}(y) \), then the limit is this sparse vector, and when \( x^{(n)} \) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1 + \tau/2} ,\] \( i = 1,\dots,N \), where \( 0 < \tau < 1 \), can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for \( \tau \) approaching 0.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

I. Daubechies, S. Güntürk, Y. Wang, and Ö. Yılmaz: “The Golden ratio encoder,” IEEE Trans. Inform. Theory 56 : 10 (2010), pp. 5097–5110. MR 2808667 Zbl 1366.94231 ArXiv 0809.1257 article

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder with \[ \beta = \phi = \frac{1 + \sqrt{5}}2 ,\] the golden ratio. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. Furthermore, a formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is proposed.

Özgür Yılmaz	Related
Yang Wang	Related
Cemalettin Sinan Güntürk	Related

year	title	people

			clear

Ingrid Daubechies

Complete Bibliography

Works connected to Cemalettin Sinan Güntürk

Filter the Bibliography List