期刊文献+

稀疏随机矩阵的观测次数下界 被引量:2

Lower Bounds on the Number of Measurements of Sparse Random Matrices
下载PDF
导出
摘要 压缩感知理论中的稀疏重构问题,要将一个高维信号从它的低维投影中恢复出来,通常选用稠密随机矩阵作为观测矩阵来解决这一问题。而某些稀疏随机矩阵作为观测矩阵也可以达到这一目的。稀疏随机矩阵的特点是,在编码和重构过程中都具有较低的计算复杂度,更新方便,且对存储容量的要求较低。该文基于压缩感知理论,分别对列重固定、行重固定以及一般的稀疏随机矩阵进行了研究,当这些稀疏随机矩阵满足有限等距性质时,推导了观测次数应满足的下界条件,并对三种矩阵的性能进行了分析。以二值稀疏随机矩阵为特例,进行了仿真实验。实验结果显示,结论给出的观测次数下界是比较紧的,并验证了列重固定、行重固定的稀疏随机矩阵作为观测矩阵的可行性和实用性。 Sparse recovery problem in the theory of compressed sensing is to recover a high-dimensional signal from its low-dimensional projection, and a dense random matrix is usually used as the measurement matrix to solve this problem. While some sparse random matrices as the measurement matrices can also achieve this goal. Sparse random matrices have several attractive properties, like low computational complexity in both encoding and recovery, easy incremental updates, and low storage requirement. Based on the theory of compressed sensing, this paper investigates sparse random matrices with fixed column sparsity or fixed row sparsity and general sparse random matrices respectively, and when these sparse ran- dom matrices satisfy the restricted isometry property, the lower bound conditions that the number of measurements should satisfy are deduced, and the performance of three matrices is analysed. Binary sparse random matrices are taken as a special example to do simulation experiments. Numerical results show that, the lower bounds on the number of measurements given by this paper are tight, and the feasibility and practicability of sparse random matrices with fixed column sparsity or fixed row sparsity as the measurement matrices are verified.
出处 《信号处理》 CSCD 北大核心 2012年第8期1156-1163,共8页 Journal of Signal Processing
基金 国家自然科学基金-微软亚洲研究院联合资助项目(60933012)
关键词 压缩感知 观测矩阵 稀疏随机矩阵 有限等距性质 观测次数 compressed sensing measurement matrix sparse random matrices restricted isometry property number of measurements
  • 相关文献

参考文献12

  • 1D.L.Donoho. Compressed sensing[J].IEEE Transactions on Information Theory Apr,2006,(04):1289-1306.doi:10.1109/TIT.2006.871582.
  • 2E.J.Candès,J.Romberg,T.Tao. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information theory,2006,(02):489-509.doi:10.1109/TIT.2005.862083.
  • 3E.J.Candès,T.Tao. Near-optimal signal recovery from random projections:Universal encoding strategies[J].IEEE Transactions on Information theory,2006,(12):5406-5425.
  • 4E.J.Candès,T.Tao. Decoding by linear programming[J].IEEE Transactions on Information theory,2005,(12):4203-4215.doi:10.1109/TIT.2005.858979.
  • 5Y.Tsaig,D.L.Donoho. Extensions of compressed sensing[J].Signal Processing,2006,(03):549-571.doi:10.1016/j.sigpro.2005.05.029.
  • 6A.Gilbert,P.Indyk. Sparse recovery using sparse matrices[A].2010.937-947.
  • 7R.Berinde,P.Indyk. Sparse recovery using sparse random matrices[R].MIT-CSAIL Technical Report,Apr,2008.
  • 8R.Berinde,A.Gilbert,P.Indyk,H.Karloff, M.Strauss. Combining geometry and combinatorics:A unified approach to sparse signal recovery[A].2008.798-805.
  • 9K.Wu,X.Guo. Compressive sensing with sparse measurement matrices[A].2011.1-5.
  • 10R.G.Baraniuk. Compressive sensing[J].IEEE Signal Processing Magazine,2007,(04):118-121.doi:10.1109/MSP.2007.4286571.

同被引文献23

  • 1Donoho D L. Compressed sensing[J]. [EEE Transactions on Information Theory, 2006, 52(4): 1289-1306.
  • 2Candes E J and Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.
  • 3Candes E J, Romberg J, and Tao T. Robust uncertainty principles: exact signM reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.
  • 4Candes E J, Eldar Y C, Needell D, et al.. Compressed sensing with coherent and redundant dictionaries[J]. Applied and Computational Harmonic Analysis, 2011, 31(1): 59-73.
  • 5Zhang T. Sparse recovery with orthogonal matching pursuit under RIP[J]. IEEE Transactions on Information Theory, 2011, 57(9): 6215-6221.
  • 6Haupt J, Bajwa W, Raz G, et al.. Toepitz compressed sensing matrices with applications to sparse channel estimation[J]. IEEE Transactions Information Theory, 2010, 56(11):5862-5875.
  • 7Luo J, Liu X, and Rosenberg C. Does compressed sensing improve the throughput of wireless sensor networks?[C]. IEEE International Conference on Communications, Cape Town. 2010: 1-6.
  • 8Lee S, Pattem S, Sathiamoorthy M, et al.. Spatially-localized compressed sensing and routing in multi~hop sensor networks[C]. Proceedings of the Third International Conference on Geosensor Networks, Oxford, 2009: 11-20.
  • 9Wang Wei, Garofalakis M, and Ramchandran K. Distributed sparse random projections for refinable approximation[C]. IEEE International Symposium on Information Processing in Sensor Networks, Cambridge, 2007: 331-339.
  • 10Gilbert A and Indyk P. Sparse recovery using sparse matrices [J]. Proceedings of the IEEE, 2010, 98(6): 937-947.

引证文献2

二级引证文献20

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部