Frames for the finite world: Sampling, coding and quantization

The American Institute of Mathematics

The following compilation of participant contributions is only intended as a lead-in to the AIM workshop “Frames for the finite world: Sampling, coding and quantization.” This

material is not for public distribution.

Corrections and new material are welcomed and can be sent to workshops@aimath.org Version: Mon Aug 11 14:08:48 2008

Table of Contents

A. Participant Contributions . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Balan, Radu

2. Bodmann, Bernhard 3. Casazza, Peter

4. DeVore, Ronald

5. Fletcher, Alyson

6. Futamura, Fumiko 7. Goyal, Vivek

8. Iwen, Mark

9. Krahmer, Felix

10. Pfander, Goetz

11. Rauhut, Holger

12. Sarvotham, Shriram

13. Schnass, Karin

14. Tropp, Joel

15. Wang, Yang

16. Ward, Rachel

Chapter A: Participant Contributions

A.1 Balan, Radu

I am interested in nonlinear signal processing using redundant representations. In particular, one topic of interest is to exploit redundancy when part of information is missing, such as the phase. If sigma-delta quantization is viewed as 1-bit compression of highly redundant signal representation, absolute value of frame coefficients can be seen as compression with MSb (Most Significant bit) loss.

A.2 Bodmann, Bernhard

I am looking forward to discussing with the other attendees. Topics I would like to discuss include the following:

• Interplay between the geometry of frame paths and quantization with noise shapers.

• Frames as codes for analog transmissions. Combined treatment of errors due to quantization, noise and erasures.

• Fusion frames and efficient encoding/decoding algorithms.

A.3 Casazza, Peter

I have a significant interest in all these topics in frame theory. I hope to contribute to the advancement of the workshop as well as starting new projects in frame theory. I have several projects on related topics which I have never released to the public but will for the workshop.

A.4 DeVore, Ronald

I have interest in signal processing. One of the main goals of signal processing is to faithfully capture a signal/image as efficiently as possible in a digital format. The topics of this workshop interface this goal in many ways such as compressed sensing, analog digital conversion, sparse representations of signal and images, and compression paradigms. It will be interesting to see how these ideas fuse together to give new sensor technology.

A.5 Fletcher, Alyson

In both image processing and one-dimensional signal processing, I have worked on estimation problems involving frames. I developed bounds on estimator performance when a signal is sparse with respect to a frame, and I later applied these to obtain results on compressed sensing and source coding via compressed sensing. I hope during the workshop to broaden this line of work, including possibly to develop connections with state-space formulations.

A.6 Futamura, Fumiko

I am currently working on a way of efficiently and optimally choosing a collection of localized frames to almost diagonalize a given set of matrices/operators, using ideas from Aldroubi, Cabrelli and Molter’s recent paper, Optimal Non-Linear Models for Sparsity and Sampling. Their general results apply specifically to the compressed sensing problem of finding a dictionary where signals have sparse representation. I would like to understand how to interpret these new results in the realm of compressed sensing.

A.7 Goyal, Vivek

Investigating the properties and applications of frame representations—especially the effect of quantization—has been one of my enduring interests. It is nice to see the topic of compressed sensing renew interest in this field.

In addition to understanding the effects of quantization in sampling (both above and below Nyquist rate), I am interested in other issues at the interface between the mathematical models for data acquisition and real implementations.

For example, this has prompted study of mitigation of jitter—the deviation between desired sampling times and actual sampling times. I am also interested in designing data acquisition systems based on computations to be computed from the data rather than for low reconstruction error of the signal itself; one approach is called functional quantization.

A.8 Iwen, Mark

I am interested in fast deterministic algorithms for sparse Trigonometric polynomial interpolation. For specifically, I am interested in the following problems: Let f be a kterm trigonometric polynomial of maximum degree N, N >> k, from which we can acquire block-box samples. How do we recover f deterministically (i.e., no probability of failure whatsoever) using as few samples as possible? How fast can we make any such procedure?

Known deterministic Fourier results include:

(i) A deterministic Fourier reconstruction algorithms which returns f using O(k^{2} log^{O(1)}(N))- time/samples. The sample sets are highly structured in this case.

(ii) A Las Vegas algorithm (with O(k^{2}N log^{2}(N)) expected runtime) for generating a set of O(k^{2} log^{2}(N)) sample positions for a discrete N-length array A which allows A’s DFT to be found deterministically by a very simple greedy algorithm (or OMP [see “Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit”, by S. Kunis and H. Rauhut]). The upshot of this result is that most sample sets of size O(k^{2} log^{O(1)}(N)) are good enough to provide guaranteed Fourier reconstructions for all k-sparse signals. Unfortunately, its known that any OMP-like greedy recovery procedure requires about this many samples to be deterministic (observed by Holger Rauhut, ...). In other words, there isnt much room for improvement using such greedy approaches.

I would be interested in discussing possible alternative recovery conditions to the RIP which are checkable in polynomial time (thus yielding Las Vegas algorithms for guaranteed deterministic sample sets). This is the idea behind (ii) which essentially relies on building an approximate discrete Dirac delta function. Perhaps algorithmic improvements to the recovery procedure may be possible which in turn allow smaller sample sets to provide guaranteed recovery(?).

Ultimately, I am interested in the following (very difficult?) question: Is it possible to recover a k-term Trigonometric polynomial deterministically in O(k log^{O(1)}(N))-time? If so, what is an algorithm that achieves this runtime?

A.9 Krahmer, Felix

My research interest comprises two areas within signal processing. My dissertation focuses on improving the accuracy of Sigma-Delta Quantization schemes. In another work with Götz Pfander and Peter Rashkov, we have studied uncertainty principles for the short time Fourier transform on finite Abelian groups.

My dissertation is concerned with the fundamental limits of accuracy in the coarse quantization of bandlimited signals. Currently, I am working on optimizing exponential error decay bounds for Sigma-Delta quantization. My research follows a work by Sinan Güntürk and examines more general finite difference schemes of the form

v_{n} − (h ∗ v)_{n} = y_{n} − q_{n},  (1)

with the quantization rule

q_{n} = sign (y_{n} + (h ∗ v)_{n})  (2)

where h is a finitely supported sequence satisfying

δ^{0} − h = Δ^{m}g  (3)

for some finitely supported sequence g . Here, δ^{k} denotes the Kronecker delta sequence positioned at the point k. If for a family of h, ∥v∥_{∞} is bounded by a m-independent constant, the decay rate of the ℓ_{∞}-error in the oversampling rate λ is inverse proportional to ∥g∥_{1}.

A sufficient condition for a uniform bound on ∥v∥_{∞} is a uniform bound

∥h∥_{1} ≤ C.  (4)

In a joint work with Percy Deift and Sinan Güntürk, we showed that the non-zero entries for the vector h with minimal support size m that leads to the optimal decay rate follows the zero locations of the Chebyshev polynomials of the second kind. Numerical experiments show that the optimal solutions, while not maximally sparse, still show a very sparse structure. This suggests a connection between the ℓ_{1}-minimization problem and sparse vectors, analogously to compressed sensing problems. During the workshop, I hope to deepen my understanding of the relation between sparseness and ℓ_{1}-minimization in the theory of compressed sensing. I am looking forward to discussions with researchers from both fields exploring the relation between the problems.

My work with Götz Pfander and Peter Rashkov has applications in operator identification and compressed sensing. In the workshop, I hope for a unified discussion comprising my interest areas, allowing to relate my different projects to each other.

In addition, I suggest open problems within the area of coarse quantization:

• How can the general lower bounds for the error decay when the sampling rate increases be refined to bounds which are specific to coarse quantization?

• Right now, the exponential bounds for the error decay of Sigma-Delta schemes work for arbitrary bounded sequences of numbers as inputs. How can the fact that we consider fine samples of a bandlimited function be better taken into account?

A.10 Pfander, Goetz

My interests in frames in finite dimensions stems from our work on a sampling/identification problem for time–varying operators. It turned out that to solve a particular continuous time problem, the construction of an N dimensional “prototype” vector with the following property was needed: any N vectors from the system of N^{2} time-frequency shifted copies of the prototype vector are linearly independent. We were able to show the existence of such a vector for N prime, but to solve our original continuous time problem in full, some composite numbers need to be considered. This open problem continues to motivate me to investigate a number of aspects of time-frequency/Gabor dictionaries in finite dimensional space, e.g., uncertainty principles and the use of the time-frequency system as measurement matrix for sparse signals.

A.11 Rauhut, Holger

I am generally working in compressed sensing and I would like to have discussions on the recent developments and problems in this area. More specifically - motivated by radar and the operator identification problem - matrices whose rows are time-frequency shifts of a fixed vector are interesting in the context of compressed sensing. It would be nice to make progress on recovery results for such matrices.

A.12 Sarvotham, Shriram

My main interest is in the Geometry of Compressed Sensing (CS) matrices. A CS matrix can be viewed as a collection of column vectors that form a frame. I am seeking to understand the properties of the “best” Compressed Sensing matrix for a given problem size. We measure the problem size using three variables: signal length (n), number of measurements (m) and the number of non-zero coefficients –sparsity– in the signal (k); the CS matrix is of dimension m x n. The quality of a CS matrix can be measured in terms of metrics such as the Restricted Isometry Property (RIP).

I have derived two converse bounds for RIP of the CS matrix in terms of the problem size n, m and k. The first bound is based on results from algebra of Singular Value Decomposition (SVD) of sub-matrices. The second bound (packing bound) is based on sphere packing arguments which we motivate by showing the equivalence of the RIP measure and codes on grassmannian spaces. The derivation of the two bounds offer rich geometric interpretation and illuminate the relationship between CS matrices and many diverse concepts such as equi-angular tight frames, codes on Euclidean spheres, and the generalized Pythagorean Theorem.

A.13 Schnass, Karin

I’d like to find a (reference to a) proof of a statement of the form:

Given a d × N matrix X with ’random’ entries, e.g. iid. following a subgaussian distribution, what is the probability that the Euclidean ball B^{d} is included in the image under X of the scaled cube \frac{K(N/d)}{\sqrt{N}}X(Q^{N})?

P (B^{d} ⊆ \frac{K(N/d)}{\sqrt{N}}X(Q^{N})) = 1 − ϵ.  (5)

K(N/d) should be of the order O(1) and ideally decrease as N → ∞. ϵ should be small, rapidly decreasing as N → ∞, e.g. like ≈ e^{−αN}.

Similar statements can be found for the case where N is very close to d, e.g. N = 2d, cp. ’Uncertainty principles and vector quantization’ by R. Vershynin and Y. Lyubarskii and references therein. However, for our problem in dictionary learning, cp. ’Dictionary identifiability from few training samples’, Remi Gribonval and I need the case where d is fixed and N is allowed to grow arbitrarily large.

A.14 Tropp, Joel

I’ve been working on algorithms for frame partitioning and effective versions of the Feichtinger conjecture. I have recently established that there are polynomial-time algorithms for forming partitions that almost satisfy the Feichtinger conjecture. In certain situations, e.g., for incoherent frames, it is even sufficient to use a random partition.

I’m interested in whether these partitions can be used to support new algorithms for solving computational problems involving frames, such as sparse approximation.

A.15 Wang, Yang

This sounds like a very interesting workshop. From my own research perspective, I would like to see discussions on the latest development on finite frames and their applications to signal processing and coding. Another area of great interest to me would be the connection of finite frames to compressive sensing. I have done a lot of research in the area of Analogto-Digital Conversion. I hope to share my research with attendees of the workshop.

A.16 Ward, Rachel

I have done some work in analog-to-digital conversion, and other work in compressed sensing. I would like to bridge these two topics for my thesis, and I hope to gain insight and ideas from this workshop.