March  2022, 21(3): 1093-1107. doi: 10.3934/cpaa.2022011

Uniform Approximation Property of Frames with Applications to Erasure Recovery

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China

* Corresponding author

Received  April 2021 Revised  November 2021 Published  March 2022 Early access  December 2021

Fund Project: This work was partially supported by the National Natural Science Foundation of China (11801282, 12101329 and 12171250) and the Fundamental Research Funds for the Central Universities

In this paper, we introduce frames with the uniform approximation property (UAP). We show that with a UAP frame, it is efficient to recover a signal from its frame coefficients with one erasure while the recovery error is smaller than that with the ordinary recovery algorithm. In fact, our approach gives a balance between the recovery accuracy and the computational complexity.

Citation: Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011
References:
[1]

A. S. BandeiraM. FickusD. G. Mixon and P. Wong, The road to deterministic matrices with the restricted isometry property, J. Fourier Anal. Appl., 19 (2013), 1123-1149.  doi: 10.1007/s00041-013-9293-2.

[2]

B. G. Bodmann, P. G. Casazza, D. Edidin and R. Balan, Frames for linear reconstruction without phase, in 2008 42nd Annual Conference on Information Sciences and Systems, 2008,721–726.

[3]

B. G. Bodmann, Optimal linear transmission by loss-insensitive packet encoding, Appl. Comput. Harmon. Anal., 22 (2007), 274-285.  doi: 10.1016/j.acha.2006.07.003.

[4]

B. G. Bodmann and N. Hammen, Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41 (2015), 317-331.  doi: 10.1007/s10444-014-9359-y.

[5]

B. G. Bodmann and V. I. Paulsen, Frames, graphs and erasures, Linear Algebra Appl., 404 (2005), 118-146.  doi: 10.1016/j.laa.2005.02.016.

[6]

B. G. BodmannV. I. Paulsen and M. Tomforde, Equiangular tight frames from complex Seidel matrices containing cube roots of unity, Linear Algebra Appl., 430 (2009), 396-417.  doi: 10.1016/j.laa.2008.08.002.

[7]

P. G. Casazza and J. Kovačević, Equal-norm tight frames with erasures, Adv. Comput. Math., 18 (2003), 387-430.  doi: 10.1023/A:1021349819855.

[8]

Q. ChengF. Lv and W. Sun, Frames of uniform subframe bounds with applications to erasures, Linear Algebra Appl., 555 (2018), 186-200.  doi: 10.1016/j.laa.2018.05.025.

[9]

O. Christensen, An Introduction to Frames and Riesz Bases, Birkhäuser/Springer, Cham, 2016. doi: 10.1007/978-3-319-25613-9.

[10]

I. Daubechies, Ten lectures on wavelets, vol. 61 of CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. doi: 10.1137/1.9781611970104.

[11]

M. FickusJ. JasperE. J. King and D. G. Mixon, Equiangular tight frames that contain regular simplices, Linear Algebra Appl., 555 (2018), 98-138.  doi: 10.1016/j.laa.2018.06.004.

[12]

M. FickusJ. JasperD. G. MixonJ. D. Peterson and C. E. Watson, Equiangular tight frames with centroidal symmetry, Appl. Comput. Harmon. Anal., 44 (2018), 476-496.  doi: 10.1016/j.acha.2016.06.004.

[13]

B. Han and Z. Xu, Robustness properties of dimensionality reduction with Gaussian random matrices, Sci. China Math., 60 (2017), 1753-1778.  doi: 10.1007/s11425-016-9018-x.

[14]

D. HanD. LarsonS. Scholze and W. Sun, Erasure recovery matrices for encoder protection, Appl. Comput. Harmon. Anal., 48 (2020), 766-786.  doi: 10.1016/j.acha.2018.09.004.

[15]

D. HanF. Lv and W. Sun, Recovery of signals from unordered partial frame coefficients, Appl. Comput. Harmon. Anal., 44 (2018), 38-58.  doi: 10.1016/j.acha.2016.04.002.

[16]

D. Han and W. Sun, Reconstruction of signals from frame coefficients with erasures at unknown locations, IEEE Trans. Inform. Theory, 60 (2014), 4013-4025.  doi: 10.1109/TIT.2014.2320937.

[17]

T. Hoffman and J. P. Solazzo, Complex equiangular tight frames and erasures, Linear Algebra Appl., 437 (2012), 549-558.  doi: 10.1016/j.laa.2012.01.024.

[18]

R. B. Holmes and V. I. Paulsen, Optimal frames for erasures, Linear Algebra Appl., 377 (2004), 31-51.  doi: 10.1016/j.laa.2003.07.012.

[19]

D. Larson and S. Scholze, Signal reconstruction from frame and sampling erasures, J. Fourier Anal. Appl., 21 (2015), 1146-1167.  doi: 10.1007/s00041-015-9404-3.

[20]

J. Leng and D. Han, Optimal dual frames for erasures II, Linear Algebra Appl., 435 (2011), 1464-1472.  doi: 10.1016/j.laa.2011.03.043.

[21]

J. LengD. Han and T. Huang, Optimal dual frames for communication coding with probabilistic erasures, IEEE Trans. Signal Process., 59 (2011), 5380-5389.  doi: 10.1109/TSP.2011.2162955.

[22]

J. Lopez and D. Han, Optimal dual frames for erasures, Linear Algebra Appl., 432 (2010), 471-482.  doi: 10.1016/j.laa.2009.08.031.

[23]

P. G. MasseyM. A. Ruiz and D. Stojanoff, Optimal dual frames and frame completions for majorization, Appl. Comput. Harmon. Anal., 34 (2013), 201-223.  doi: 10.1016/j.acha.2012.03.011.

[24]

P. M. Morillas, Optimal dual fusion frames for probabilistic erasures, Electron. J. Linear Algebra, 32 (2017), 191-203.  doi: 10.13001/1081-3810.3267.

[25]

S. PehlivanD. Han and R. Mohapatra, Linearly connected sequences and spectrally optimal dual frames for erasures, J. Funct. Anal., 265 (2013), 2855-2876.  doi: 10.1016/j.jfa.2013.08.012.

[26]

Y. Wang, Random matrices and erasure robust frames, J. Fourier Anal. Appl., 24 (2018), 1-16.  doi: 10.1007/s00041-016-9486-6.

show all references

References:
[1]

A. S. BandeiraM. FickusD. G. Mixon and P. Wong, The road to deterministic matrices with the restricted isometry property, J. Fourier Anal. Appl., 19 (2013), 1123-1149.  doi: 10.1007/s00041-013-9293-2.

[2]

B. G. Bodmann, P. G. Casazza, D. Edidin and R. Balan, Frames for linear reconstruction without phase, in 2008 42nd Annual Conference on Information Sciences and Systems, 2008,721–726.

[3]

B. G. Bodmann, Optimal linear transmission by loss-insensitive packet encoding, Appl. Comput. Harmon. Anal., 22 (2007), 274-285.  doi: 10.1016/j.acha.2006.07.003.

[4]

B. G. Bodmann and N. Hammen, Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41 (2015), 317-331.  doi: 10.1007/s10444-014-9359-y.

[5]

B. G. Bodmann and V. I. Paulsen, Frames, graphs and erasures, Linear Algebra Appl., 404 (2005), 118-146.  doi: 10.1016/j.laa.2005.02.016.

[6]

B. G. BodmannV. I. Paulsen and M. Tomforde, Equiangular tight frames from complex Seidel matrices containing cube roots of unity, Linear Algebra Appl., 430 (2009), 396-417.  doi: 10.1016/j.laa.2008.08.002.

[7]

P. G. Casazza and J. Kovačević, Equal-norm tight frames with erasures, Adv. Comput. Math., 18 (2003), 387-430.  doi: 10.1023/A:1021349819855.

[8]

Q. ChengF. Lv and W. Sun, Frames of uniform subframe bounds with applications to erasures, Linear Algebra Appl., 555 (2018), 186-200.  doi: 10.1016/j.laa.2018.05.025.

[9]

O. Christensen, An Introduction to Frames and Riesz Bases, Birkhäuser/Springer, Cham, 2016. doi: 10.1007/978-3-319-25613-9.

[10]

I. Daubechies, Ten lectures on wavelets, vol. 61 of CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. doi: 10.1137/1.9781611970104.

[11]

M. FickusJ. JasperE. J. King and D. G. Mixon, Equiangular tight frames that contain regular simplices, Linear Algebra Appl., 555 (2018), 98-138.  doi: 10.1016/j.laa.2018.06.004.

[12]

M. FickusJ. JasperD. G. MixonJ. D. Peterson and C. E. Watson, Equiangular tight frames with centroidal symmetry, Appl. Comput. Harmon. Anal., 44 (2018), 476-496.  doi: 10.1016/j.acha.2016.06.004.

[13]

B. Han and Z. Xu, Robustness properties of dimensionality reduction with Gaussian random matrices, Sci. China Math., 60 (2017), 1753-1778.  doi: 10.1007/s11425-016-9018-x.

[14]

D. HanD. LarsonS. Scholze and W. Sun, Erasure recovery matrices for encoder protection, Appl. Comput. Harmon. Anal., 48 (2020), 766-786.  doi: 10.1016/j.acha.2018.09.004.

[15]

D. HanF. Lv and W. Sun, Recovery of signals from unordered partial frame coefficients, Appl. Comput. Harmon. Anal., 44 (2018), 38-58.  doi: 10.1016/j.acha.2016.04.002.

[16]

D. Han and W. Sun, Reconstruction of signals from frame coefficients with erasures at unknown locations, IEEE Trans. Inform. Theory, 60 (2014), 4013-4025.  doi: 10.1109/TIT.2014.2320937.

[17]

T. Hoffman and J. P. Solazzo, Complex equiangular tight frames and erasures, Linear Algebra Appl., 437 (2012), 549-558.  doi: 10.1016/j.laa.2012.01.024.

[18]

R. B. Holmes and V. I. Paulsen, Optimal frames for erasures, Linear Algebra Appl., 377 (2004), 31-51.  doi: 10.1016/j.laa.2003.07.012.

[19]

D. Larson and S. Scholze, Signal reconstruction from frame and sampling erasures, J. Fourier Anal. Appl., 21 (2015), 1146-1167.  doi: 10.1007/s00041-015-9404-3.

[20]

J. Leng and D. Han, Optimal dual frames for erasures II, Linear Algebra Appl., 435 (2011), 1464-1472.  doi: 10.1016/j.laa.2011.03.043.

[21]

J. LengD. Han and T. Huang, Optimal dual frames for communication coding with probabilistic erasures, IEEE Trans. Signal Process., 59 (2011), 5380-5389.  doi: 10.1109/TSP.2011.2162955.

[22]

J. Lopez and D. Han, Optimal dual frames for erasures, Linear Algebra Appl., 432 (2010), 471-482.  doi: 10.1016/j.laa.2009.08.031.

[23]

P. G. MasseyM. A. Ruiz and D. Stojanoff, Optimal dual frames and frame completions for majorization, Appl. Comput. Harmon. Anal., 34 (2013), 201-223.  doi: 10.1016/j.acha.2012.03.011.

[24]

P. M. Morillas, Optimal dual fusion frames for probabilistic erasures, Electron. J. Linear Algebra, 32 (2017), 191-203.  doi: 10.13001/1081-3810.3267.

[25]

S. PehlivanD. Han and R. Mohapatra, Linearly connected sequences and spectrally optimal dual frames for erasures, J. Funct. Anal., 265 (2013), 2855-2876.  doi: 10.1016/j.jfa.2013.08.012.

[26]

Y. Wang, Random matrices and erasure robust frames, J. Fourier Anal. Appl., 24 (2018), 1-16.  doi: 10.1007/s00041-016-9486-6.

[1]

Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau. Density, overcompleteness, and localization of frames. Electronic Research Announcements, 2006, 12: 71-86.

[2]

Manuel V. C. Vieira. Derivatives of eigenvalues and Jordan frames. Numerical Algebra, Control and Optimization, 2016, 6 (2) : 115-126. doi: 10.3934/naco.2016003

[3]

Hanbing Liu, Yongdong Huang, Chongjun Li. Weaving K-fusion frames in hilbert spaces. Mathematical Foundations of Computing, 2020, 3 (2) : 101-116. doi: 10.3934/mfc.2020008

[4]

Mike Crampin, Tom Mestdag. Reduction of invariant constrained systems using anholonomic frames. Journal of Geometric Mechanics, 2011, 3 (1) : 23-40. doi: 10.3934/jgm.2011.3.23

[5]

Amir Averbuch, Pekka Neittaanmäki, Valery Zheludev. Periodic spline-based frames for image restoration. Inverse Problems and Imaging, 2015, 9 (3) : 661-707. doi: 10.3934/ipi.2015.9.661

[6]

P. Cerejeiras, M. Ferreira, U. Kähler, F. Sommen. Continuous wavelet transform and wavelet frames on the sphere using Clifford analysis. Communications on Pure and Applied Analysis, 2007, 6 (3) : 619-641. doi: 10.3934/cpaa.2007.6.619

[7]

Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761

[8]

Kazuhiro Sakai. The oe-property of diffeomorphisms. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 581-591. doi: 10.3934/dcds.1998.4.581

[9]

Pablo Sánchez, Jaume Sempere. Conflict, private and communal property. Journal of Dynamics and Games, 2016, 3 (4) : 355-369. doi: 10.3934/jdg.2016019

[10]

Konstantinos Drakakis, Scott Rickard. On the generalization of the Costas property in the continuum. Advances in Mathematics of Communications, 2008, 2 (2) : 113-130. doi: 10.3934/amc.2008.2.113

[11]

Kazumine Moriyasu, Kazuhiro Sakai, Kenichiro Yamamoto. Regular maps with the specification property. Discrete and Continuous Dynamical Systems, 2013, 33 (7) : 2991-3009. doi: 10.3934/dcds.2013.33.2991

[12]

Peng Sun. Minimality and gluing orbit property. Discrete and Continuous Dynamical Systems, 2019, 39 (7) : 4041-4056. doi: 10.3934/dcds.2019162

[13]

Bo Su. Doubling property of elliptic equations. Communications on Pure and Applied Analysis, 2008, 7 (1) : 143-147. doi: 10.3934/cpaa.2008.7.143

[14]

Martin Swaczyna, Petr Volný. Uniform motions in central fields. Journal of Geometric Mechanics, 2017, 9 (1) : 91-130. doi: 10.3934/jgm.2017004

[15]

Younghun Hong, Changhun Yang. Uniform Strichartz estimates on the lattice. Discrete and Continuous Dynamical Systems, 2019, 39 (6) : 3239-3264. doi: 10.3934/dcds.2019134

[16]

Mickaël Kourganoff. Uniform hyperbolicity in nonflat billiards. Discrete and Continuous Dynamical Systems, 2018, 38 (3) : 1145-1160. doi: 10.3934/dcds.2018048

[17]

Se-Hyun Ku. Expansive flows on uniform spaces. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1585-1598. doi: 10.3934/dcds.2021165

[18]

Jinjun Li, Min Wu. Generic property of irregular sets in systems satisfying the specification property. Discrete and Continuous Dynamical Systems, 2014, 34 (2) : 635-645. doi: 10.3934/dcds.2014.34.635

[19]

Rafael Potrie. Partially hyperbolic diffeomorphisms with a trapping property. Discrete and Continuous Dynamical Systems, 2015, 35 (10) : 5037-5054. doi: 10.3934/dcds.2015.35.5037

[20]

Björn Gebhard. A note concerning a property of symplectic matrices. Communications on Pure and Applied Analysis, 2018, 17 (5) : 2135-2137. doi: 10.3934/cpaa.2018101

2020 Impact Factor: 1.916

Metrics

  • PDF downloads (141)
  • HTML views (115)
  • Cited by (0)

Other articles
by authors

[Back to Top]