Frames for the finite world: Sampling, coding and quantization

August 18-22, 2008, American Institute of Mathematics, Palo Alto, CA.

Organizers: Sinan Gunturk, Goetz Pfander, Holger Rauhut, and Ozgur Yilmaz

Workshop Organization

Timetable for Days 1, 2, and 3:

9:00a	Morning talk (part 1)
	Coffee break
11:00a	Morning talk (part 2)
	Lunch break
2:00p	Afternoon discussion in groups

The topics and the schedule for Days 4 and 5 will be arranged depending on the developments during the first three days of the workshop.

There will be a closing session on Friday afternoon.

There will be a banquet on Tuesday evening. Details will follow...

Day 1

Theme: Concrete Frames

Possible afternoon discussion groups:

Classification of existing frame designs according to their key properties (e.g., various definitions / interpretations of well-distribution)

Sample literature / overview (not meant to be complete):

T. Strohmer, A note on equiangular tight frames (preprint).
G. Kutyniok, A. Pezeshki, R. Calderbank, and T. Liu, Robust Dimension Reduction, Fusion Frames, and Grassmannian Packings, Appl. Comput. Harmon. Anal., to appear.
F. Kramer, G.E. Pfander, P. Rashkov Uncertainty in time–frequency representations on finite Abelian groups and applications Applied and Computational Harmonic Analysis Volume 25, Issue 2, September 2008, Pages 209-225
Bernhard G. Bodmann, Peter G. Casazza, Dan Edidin and Radu Balan, Frames for Linear Reconstruction without Phase, Proceedings of the 42nd Conference on Information Sciences and Systems, Princeton University, NJ, pp. 721-726, 2008.
J. Kovacevic, A. Chebira Life beyond bases: The advent of frames (Part I) IEEE SP Mag., vol. 24, no. 4, Jul. 2007, pp. 86-104.
J. Kovacevic, A. Chebira Life beyond bases: The advent of frames (Part II) IEEE SP Mag., vol. 24, no. 5, Sep. 2007, pp. 115-125.
P. Casazza, M. Fickus Chirps on Finite cyclic groups EURASIP J. Appl. Signal Process. 2006, Frames and overcomplete representations in signal processing, communications, and information theory, Art. ID 70204, 7 pp.
P.G. Casazza, M. Fickus, J. Kovacevic, M.T. Leon, J.C. Tremain A Physical Interpretation for Finite Tight Frames Harmonic analysis and applications, 51--76, Appl. Numer. Harmon. Anal., Birkhäuser Boston, Boston, MA, 2006.
P.G. Casazza, M.T. Leon Existence and Construction of Finite Tight Frames J. Concr. Appl. Math. 4 (2006), no. 3, 277--289.
J. Lawrence, G.E. Pfander, D. Walnut Linear independence of Gabor systems in finite dimensional vector spaces Journal of Fourier Analysis and Applications, 11(6), pp. 715-726, 2005
P. Casazza, N. Leonhard The Known Equal Norm Parseval Frames as of 2005
R.B. Holmes,V.I. Paulsen Optimal frames for erasures Linear Algebra and its Applications Volume 377, 15 January 2004, Pages 31-51.
P.G. Casazza Custom Building Finite Frames Wavelets, frames and operator theory, 61--86, Contemp. Math., 345, Amer. Math. Soc., Providence, RI, 2004.
P. G. Casazza and G. Kutyniok, Frames of Subspaces, Wavelets, Frames and Operator Theory (College Park, MD, 2003), 87-113, Contemp. Math. 345, Amer. Math. Soc., Providence, RI, 2004.
P.G. Casazza, J. Kovacevic Equal-norm Tight Frames with Erasures, Advances in Comp. Math., vol. 18 (2-4), pp. 387-430 (2003)
T. Strohmer, R.W. Heath Jr., Grassmannian Frames with Applications to Coding and Communication , Appl. Comput. Harmon. Anal. 14 (2003), no. 3, 257--275.
Y. C. Eldar and H. Boelcskei Geometrically Uniform Frame IEEE Trans. Inform. Theory, vol. 49, pp. 993-1006, 2003.
J. Benedetto and M. Fickus, Finite normalized tight frames, Advances in Comp. Math., vol. 18 (2), pp. 357-385, 2003.
Y. C. Eldar and G. D. Forney, Jr. Optimal Tight Frames and Quantum Measurement IEEE Trans. Inform. Theory, vol. 48, no. 3, pp. 599-610, Mar. 2002.
Lozano, A.C.; Kovacevic, J.; Andrews, M. ;Quantized frame expansions in a wireless environment Data Compression Conference, 2002. Proceedings. DCC 2002 2-4 April 2002 Page(s):232 - 241
P.G. Casazza The Art of Frame Theory Taiwanese J. Math. 4 (2000), no. 2, 129--201.

Day 2

Theme: Design of Measurement Matrices for Compressive Sensing

Possible afternoon discussion groups:

    1. Deterministic constructions (emphasizing main properties that we seek in such constructions)
    2. Probabilistic constructions, random sampling, analog-to-information

Sample literature / overview (not meant to be complete):

    1. Deterministic constructions

Venkatesh Saligrama, Deterministic designs with deterministic guarantees: Toeplitz compressed sensing matrices, sequence design and system identification. (Preprint, 2008)
Shamgar Gurevich, Ronny Hadani, and Nir Sochen, On some deterministic dictionaries supporting sparsity. (To appear in Journal of Fourier Analysis and Applications)
Lorne Applebaum, Stephen Howard, Stephen Searle, and Robert Calderbank, Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery. (Preprint, 2008)
Sina Jafarpour, Weiyu Xu, Babak Hassibi, and Robert Calderbank, Efficient compressed sensing using high-quality expander graphs. (Preprint, 2008)
Lu Gan, Thong Do, Trac D. Tran, Fast compressive imaging using scrambled block Hadamard ensemble. (Preprint, 2008)
Venkat Chandar, A negative result concerning explicit matrices with the restricted isometry property. (Preprint, 2008)
S. D. Howard, A. R. Calderbank, and S. J. Searle, A fast reconstruction algorithm for deterministic compressive sensing using second order Reed-Muller codes. (Conf. on Info. Sciences and Systems (CISS), Princeton, New Jersey, March 2008)
Mehmet Akcakaya and Vahid Tarokh, A frame construction and a universal distortion bound for sparse representations. (IEEE Int. Symposium on Information Theory (ISIT), Nice, France, June 2007)
Weiyu Xu and Babak Hassibi, Efficient compressive sensing with deterministic guarantees using expander graphs. (IEEE Information Theory Workshop, Lake Tahoe, September 2007)
Venkatesan Guruswami, James R. Lee, and Alexander Razborov, Almost Euclidean subspaces of ell-1-N via expander codes. (Electronic Colloquium on Computational Complexity, Report TR07-089, September, 2007)
Mark Iwen, A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods. (Preprint, 2007)
Boris S. Kashin and Vladimir N. Temlyakov, A remark on compressed sensing. (Mathematical Notes, 82(5-6), pp. 748 - 755, Nov. 2007)
Piotr Indyk, Explicit constructions for compressed sensing of sparse signals. (Proc. of the 9th Symposium on Discrete Algorithms, 2008)
Ronald A. DeVore, Deterministic constructions of compressed sensing matrices. (J. of Complexity, 23, pp. 918 - 925, August 2007)

2. Probabilistic constructions, random sampling

Justin Romberg, Compressive sensing by random convolution. (Preprint, 2008)
Florian Sebert, Leslie Ying, and Yi Ming Zou, Toeplitz block matrices in compressed sensing. (Preprint, 2008)
Thong T. Do, Trac D. Tran, and Lu Gan, Fast compressive sampling with structurally random matrices. (Preprint, 2007)
Waheed Bajwa, Jarvis Haupt, Gil Raz, Stephen Wright, and Robert Nowak, Toeplitz-structured compressed sensing matrices. (IEEE Workshop on Statistical Signal Processing (SSP), Madison, Wisconsin, August 2007)
Radu Berinde and Piotr Indyk, Sparse recovery using sparse random matrices. (Preprint, 2008)
Mark Rudelson, RomanVershynin, On sparse reconstruction from Fourier and Gaussian measurements, Communications on Pure and Applied Mathematics 61 (2008), 1025-1045.
Holger Rauhut, Stability results for random sampling of sparse trigonometric polynomials. (Preprint, 2006)
Holger Rauhut, Random sampling of sparse trigonometric polynomials. (Applied and Computational Harmonic Analysis, 22(1), pp. 16-42, Jan. 2007)
Emmanuel Candès, Justin Romberg, and Terence Tao, Stable signal recovery from incomplete and inaccurate measurements. (Communications on Pure and Applied Mathematics, 59(8), pp. 1207-1223, August 2006)
Mark Rudelson and Roman Vershynin, Geometric approach to error correcting codes and reconstruction of signals. (International Mathematical Research Notices, 64, pp. 4019 - 4041, 2005)
Emmanuel Candès and Justin Romberg, Practical signal recovery from random projections. (Preprint, Jan. 2005)
Emmanuel Candès and Terence Tao, Near optimal signal recovery from random projections: Universal encoding strategies? (IEEE Trans. on Information Theory, 52(12), pp. 5406 - 5425, December 2006)
Emmanuel Candès and Justin Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions. (Foundations of Comput. Math., 6(2), pp. 227 - 254, April 2006)
David Donoho, Compressed sensing. (IEEE Trans. on Information Theory, 52(4), pp. 1289 - 1306, April 2006)
Emmanuel Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. (IEEE Trans. on Information Theory, 52(2) pp. 489 - 509, February 2006)

Day 3

Theme: Quantization Theory for Frames

Possible afternoon discussion groups:

    1. Rate-distortion theory for frames, especially finite frames
    2. Sigma-Delta and beta encoding
    3. A/D conversion and compressive sensing

Sample literature / overview (not meant to be complete):

    1. A/D Conversion and compressive sensing

Vivek K Goyal, Alyson K. Fletcher, and Sundeep Rangan, Compressive sampling and lossy compression. (IEEE Signal Processing Magazine, 25(2), pp. 48-56, March 2008)
Petros Boufounos and Richard G. Baraniuk, 1-Bit compressive sensing. (Conf. on Info. Sciences and Systems (CISS), Princeton, New Jersey, March 2008)
Petros Boufounos and Richard G. Baraniuk, Sigma delta quantization for compressive sensing. (Preprint, 2007)
Alyson K. Fletcher, Sundeep Rangan, and Vivek K Goyal, Rate-distortion bounds for sparse approximation. (IEEE Statistical Signal Processing Workshop (SSP), Madison, Wisconsin, August 2007)
Alyson K. Fletcher, Sundeep Rangan, and Vivek K Goyal, On the Rate-Distortion Performance of Compressed Sensing. (IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Honolulu, Hawaii, April 2007)
Petros Boufounos and Richard Baraniuk, Quantization of sparse representations. (Rice ECE Department Technical Report TREE 0701 - Summary appears in Proc. Data Compression Conference (DCC), Snowbird, Utah, March 2007)
Alyson K. Fletcher, Sundeep Rangan, Vivek K Goyal, and Kannan Ramchandran, Denoising by sparse approximation: Error bounds based on rate-distortion theory. (EURASIP J. Applied Signal Processing, 2006, Article ID 26318.)

2. Finite frames and Quantization

M. Lammers, A. Powell, and O. Yilmaz, Alternative dual frames for digital-to-analog conversion in sigma-delta quantization, Advances in Computational Mathematics, accepted.
B. G. Bodmann and S. P. Lipshitz, Randomly Dithered Quantization and Sigma-Delta Noise Shaping for Finite Frames, Appl. Comput. Harmon. Anal., to appear (2008)
Y. Wang, Sigma-delta quantization errors and the traveling salesman problem, Adv. Comput. Math. 28 (2008), no. 2, 101--118.
M. Lammers, A. Powell, and O. Yilmaz, On quantization of finite frame expansions: sigma-delta schemes of arbitrary order, SPIE, Wavelets XII, San Diego, Aug. 2007.
D. Jimenez; L. Wang, and Y. Wang, White noise hypothesis for uniform quantization errors. SIAM J. Math. Anal. 38 (2007), no. 6, 2042--2056
B. G. Bodmann, V. I. Paulsen and S. Abdulbaki, Smooth frame path termination for higher order sigma-delta quantization, J. Fourier Anal. Appl. 13, 285-307 (2007).
B. G. Bodmann and V. I. Paulsen, Frame Paths and Error Bounds for Sigma-Delta Quantization, Appl. Comput. Harmon. Anal. 22, 176-197, (2007).
P. Boufounos and A. Oppenheim, Quantization Noise Shaping on Arbitrary Frame Expansions, EURASIP Journal on Applied Signal Processing, vol. 2006, Article ID 53807 (2006)
J. Benedetto, A. Powell, and O. Yilmaz, Second order Sigma-Delta quantization of finite frame expansions, Applied and Computational Harmonic Analysis, Vol. 20 (1), (2006), pp. 126-148.
J. Benedetto, A. Powell, and O. Yilmaz, Sigma-Delta quantization and finite frames, IEEE Transactions on Information Theory, Vol. 52 (5), (2006), pp. 1990-2005.
V. Goyal, J. Kovacevic, J.A. Kelner Quantized Frame Expansions with Erasures Applied and Computational Harmonic Analysis Volume 10, Issue 3, May 2001, Pages 203-233.
V. Goyal, M. Vetterli, and N. Thao, Quantized overcomplete expansions in R^N: analysis, synthesis, and algorithms, IEEE Transactions on Information Theory, vol. 44 (1), pp. 16-31 (1998)

3. Sigma-Delta and Beta Encoders (General)

I. Daubechies, R. DeVore, S. Gunturk and V. Vaishampayan, A/D Conversion with Imperfect Quantizers, IEEE Transactions on Information Theory, 52 (3):874-885, March 2006.
S. Gunturk and N. Thao, Ergodic Dynamics in Sigma-Delta Quantization: Tiling Invariant Sets and Spectral Analysis of Error, Advances in Applied Mathematics, 34 (2005), 523-560.
S. Gunturk, One-Bit Sigma-Delta Quantization with Exponential Accuracy, Communications on Pure and Applied Mathematics, vol. 56, pp. 1608-1630, no. 11, 2003.
I. Daubechies and R. DeVore, Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order, Annals of Math., 158 (2), pp.679-710, 2003.