nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On Reconstructing Functions from Binary Measurements

verfasst von : Robert Calderbank, Anders Hansen, Bogdan Roman, Laura Thesing

Erschienen in: Compressed Sensing and Its Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the problem of reconstructing a function from linear binary measurements. That is, the samples of the function are given by inner products with functions taking only the values 0 and 1. We consider three particular methods for this problem, the parameterized-background data-weak (PBDW) method, generalized sampling and infinite-dimensional compressed sensing. The first two methods are dependent on knowing the stable sampling rate when considering samples by Walsh function and wavelet reconstruction. We establish linearity of the stable sampling rate, which is sharp, allowing for optimal use of these methods. In addition, we provide recovery guaranties for infinite-dimensional compressed sensing with Walsh functions and wavelets.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Quantized Compressed Sensing: A Survey

Nächstes Kapitel Classification Scheme for Binary Data with Extensions

The STOne matrix is an orthogonal matrix that provides universality like random matrices do. However, it was invented for many other purposes. It has a fast \(\mathcal {O}(N\log N)\) transform and allows multi-scale image recovery from compressive measurements: low-resolution previews can be quickly generated by applying the fast transform on the measurements directly, and high-resolution recovery is possible from the same measurements via CS solvers. In addition, it allows efficient recovery of compressive videos when sampling in a semi-random manner.

B. Adcock, A. Hansen, G. Kutyniok, J. Ma, Linear stable sampling rate: optimality of 2d wavelet reconstructions from fourier measurements. SIAM J. Math. Anal. 47(2), 1196–1233 (2015)MathSciNetCrossRef

B. Adcock, A. Hansen, C. Poon, Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem. SIAM J. Math. Anal. 45(5), 3132–3167 (2013)MathSciNetCrossRef

B. Adcock, A. Hansen, C. Poon, B. Roman, Breaking the coherence barrier: a new theory for compressed sensing. Forum Math. Sigma 5 (2017)

B. Adcock, A.C. Hansen, A generalized sampling theorem for stable reconstructions in arbitrary bases. J. Fourier Anal. Appl. 18(4), 685–716 (2010)MathSciNetCrossRef

B. Adcock, A.C. Hansen, Generalized sampling and infinite-dimensional compressed sensing. Found. Comput. Math. 16(5), 1263–1323 (2016)MathSciNetCrossRef

B. Adcock, A.C. Hansen, C. Poon, On optimal wavelet reconstructions from Fourier samples: linearity and universality of the stable sampling rate. Appl. Comput. Harmon. Anal. 36(3), 387–415 (2014)MathSciNetCrossRef

B. Adcock, A. C. Hansen, C. Poon, B. Roman, Breaking the coherence barrier: a new theory for compressed sensing, in Forum of Mathematics, Sigma, volume 5. Cambridge University Press (2017)

A. Aldroubi, M. Unser, A general sampling theory for nonideal acquisition devices. IEEE Trans. Signal Process. 42(11), 2915–2925 (1994)CrossRef

V. Antun, Coherence estimates between hadamard matrices and daubechies wavelets. Master’s thesis, University of Oslo (2016)

10.

M. Bachmayr, A. Cohen, R. DeVore, G. Migliorati, Sparse polynomial approximation of parametric elliptic pdes. part ii: lognormal coefficients. ESAIM: Math. Modell. Numer. Anal. 51(1), 341–363 (2017)

11.

R. Baraniuk, V. Cevher, M. Duarte, C. Hedge, Model-based compressive sensing. IEEE T Inf. Th. 56(4) (2010)

12.

D. Baron, S. Sarvotham, R. Baraniuk, Bayesian compressive sensing via belief propagation. IEEE T Sig. Proc. 58(1) (2010)

13.

P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, P. Wojtaszczyk, Data assimilation in reduced modeling. SIAM/ASA J. Uncertain. Quantif. 5(1), 1–29 (2017)MathSciNetCrossRef

14.

A. Böttcher, Infinite matrices and projection methods: in lectures on operator theory and its applications, fields inst. monogr. Amer. Math. Soc. (3), 1–72 (1996)

15.

E. Candès, D. Donoho, Recovering edges in ill-posed inverse problems: optimality of curvelet frames. Ann. Statist. 30(3) (2002)

16.

E. Candès, Y. Plan, A probabilistic and RIPless theory of compressed sensing. IEEE T Inf. Th. 57(11) (2011)

17.

E. Candès, J. Romberg, Robust signal recovery from incomplete observations, in IEEE International Conference on Image Processing (2006)

18.

E. Candès, J. Romberg, Sparsity and incoherence in compressive sampling. Inverse Problems 23(3) (2007)

19.

E. Candès, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE T Inf. Th. 52(2) (2006)

20.

A. Cohen, I. Daubechies, P. Vial, Wavelets on the interval and fast wavelet transforms. Comput. Harmon. Anal. 1(1), 54–81 (1993)MathSciNetCrossRef

21.

S. Dahlke, G. Kutyniok, P. Maass, C. Sagiv, H.-G. Stark, G. Teschke, The uncertainty principle associated with the continuous shearlet transform. Int. J. Wavelets Multiresolut. Inf. Process. 6(2) (2008)

22.

R. DeVore, G. Petrova, P. Wojtaszczyk, Data assimilation and sampling in banach spaces. Calcolo 54(3), 963–1007 (2017)MathSciNetCrossRef

23.

M. Do, M. Vetterli, The contourlet transform: an efficient directional multiresolution image representation. IEEE T Image Proc. 14(12) (2005)

24.

D. Donoho, Compressed sensing. IEEE T Inf. Th. 52(4) (2006)

25.

D. Donoho, M. Elad, Optimally sparse representation in general (non-orthogonal) dictionaries via \(\ell _1\) minimization. Proc. Natl. Acad. Sci. USA 100 (2003)

26.

D. Donoho, A. Javanmard, A. Montanari, Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing. IEEE T Inf. Th. 59(11) (2013)

27.

D. Donoho, A. Maleki, A. Montanari, Message-passing algorithms for compressed sensing. Proc. Natl Acad. Sci. USA 106(45) (2009)

28.

M. Duarte, R. Baraniuk, Kronecker compressive sensing. IEEE T Image Proc. 21(2) (2012)

29.

T. Dvorkind, Y.C. Eldar, Robust and consistent sampling. IEEE Signal Process. Lett. 16(9), 739–742 (2009)CrossRef

30.

Y.C. Eldar, Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors. J. Fourier Anal. Appl. 9(1), 77–96 (2003)MathSciNetCrossRef

31.

Y.C. Eldar, Sampling without Input Constraints: Consistent Reconstruction in Arbitrary Spaces (Sampling, Wavelets and Tomography, 2003)

32.

Y.C. Eldar, T. Werther, General framework for consistent sampling in hilbert spaces. Int. J. Wavelets Multiresolut. Inf. Process. 3(4), 497–509 (2005)MathSciNetCrossRef

33.

S. Foucart , H. Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser (2013)

34.

S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing (Springer Science+Business Media, New York, 2013)CrossRef

35.

L. Gan, T. Do, and T. Tran, Fast compressive imaging using scrambled hadamard ensemble. Proc. Eur. Signal Proc. Conf. (2008)

36.

E. Gauss, Walsh Funktionen für Ingenieure und Naturwissenschaftler (Springer Fachmedien, Wiesbaden, 1994)CrossRef

37.

T. Goldstein, L. Xu, K. Kelly, R. Baraniuk, The stone transform: multi-resolution image enhancement and real-time compressive video. arXiv:1311.3405 (2013)

38.

K. Gröchenig, Z. Rzeszotnik, T. Strohmer, Quantitative estimates for the finite section method and banach algebras of matrices. Integr. Equ. Oper. Theory 2(67), 183–202 (2011)MATH

39.

A. Hansen, On the approximation of spectra of linear operators on hilbert spaces. J. Funct. Anal. 8(254), 2092–2126 (2008)MathSciNetCrossRef

40.

A.C. Hansen, On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators. J. Amer. Math. Soc. 24(1), 81–124 (2011)MathSciNetCrossRef

41.

A. C. Hansen, L. Thesing, On the stable sampling rate for binary measurements and wavelet reconstruction. preprint (2017)

42.

L. He, L. Carin, Exploiting structure in wavelet-based Bayesian compressive sensing. IEEE T Sig. Proc. 57(9) (2009)

43.

T. Hrycak, K. Gröchenig, Pseudospectral fourier reconstruction with the modified inverse polynomial reconstruction method. J. Comput. Phys. 229(3), 933–946 (2010)MathSciNetCrossRef

44.

G. Huang, H. Jiang, K. Matthews, P. Wilford, Lensless imaging by compressive sensing. IEEE Intl. Conf. Image Proc. (2013)

45.

M. Khajehnejad, W. Xu, A. Avestimehr, B. Hassibi, Analyzing weighted \(\ell _1\) minimization for sparse recovery with nonuniform sparse models. IEEE T Sig Proc. 59(5) (May 2011)

46.

F. Krzakala, M. Mézard, F. Sausset, Y. Sun, L. Zdeborová, Statistical-physics-based reconstruction in compressed sensing. Phys. Rev. X 2 (May 2012)

47.

G. Kutyniok, W.-Q. Lim, Optimal compressive imaging of fourier data. SIAM J. Imaging Sci. 11(1), 507–546 (2018)MathSciNetCrossRef

48.

M. Lindner, Infinite Matrices and their Finite Sections: An Introduction to the Limit Operator Method (Birkhäuser Verlag, Basel, 2006)MATH

49.

M. Lustig, D. Donoho, J. Pauly, Sparse MRI: the application of compressed sensing for rapid MRI imaging. Magn. Reson. Imaging 58(6) (2007)

50.

J. Ma, Generalized sampling reconstruction from fourier measurements using compactly supported shearlets. Appl. Comput. Harmon. Anal. (2015)

51.

Y. Maday, A.T. Patera, J.D. Penn, M. Yano, A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics. Int. J. Numer. Methods Eng. 102(5), 933–965 (2015)MathSciNetCrossRef

52.

S. Mallat, A Wavelet Tour of Signal Processing (Academic Press, San Diego, 1998)MATH

53.

S. Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, 3nd edn. (Academic Press, 2009)

54.

D. Needell, J. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmonic Anal. 26(3) (2009)

55.

C. Poon, Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames. Appl. Comput. Harmonic Anal. 42(3), 402–451 (2017)MathSciNetCrossRef

56.

J. Romberg, Imaging via compressive sampling. IEEE Sig. Proc. Mag. 25(2) (2008)

57.

S. Som, P. Schniter, Compressive imaging using approximate message passing and a markov-tree prior. IEEE T Sig. Proc. 60(7) (2012)

58.

V. Studer, J. Bobin, M. Chahid, H.S. Mousavi, E. Candes, M. Dahan, Compressive fluorescence microscopy for biological and hyperspectral imaging. Proc. Natl Acad. Sci. 109(26), E1679–E1687 (2012)CrossRef

59.

L. Thesing, A. Hansen. Non uniform recovery guarantees for binary measurements and wavelet reconstruction. To appear

60.

L. Thesing, A. Hansen, Linear reconstructions and the analysis of the stable sampling rate. Sampl. Theory Image Process. 17(1), 103–126 (2018)MathSciNetCrossRef

61.

J. Tropp, Greed is good: algorithmic results for sparse approximation. IEEE T Inf. Th. 50(10) (2004)

62.

J. Tropp, Just relax: convex programming methods for identifying sparse signals in noise. IEEE T Inf. Th. 52(3) (2006)

63.

Y. Tsaig, D. Donoho, Extensions of compressed sensing. Signal Process 86, 3 (2006)

64.

M. Unser, J. Zerubia, A generalized sampling theory without band-limiting constraints. IEEE Trans. Circuits Syst. II. 45(8), 959–969 (1998)CrossRef

65.

Y. Wu, S. Verdu, Rényi information dimension: fundamental limits of almost lossless analog compression. IEEE T Inf. Th. 56(8) (2010)

Titel: On Reconstructing Functions from Binary Measurements
verfasst von: Robert Calderbank
Anders Hansen
Bogdan Roman
Laura Thesing
Verlag: Springer International Publishing
Buch: Compressed Sensing and Its Applications
Print ISBN: 978-3-319-73073-8

Electronic ISBN: 978-3-319-73074-5

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-319-73074-5_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"