Block-length dependent thresholds in block-sparse compressed sensing
Block-length dependent thresholds in block-sparse compressed sensing
复制标题
DOI：
--
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
M. Stojnic
中科院分区：
文献类型：
--
作者：
M. Stojnic
压缩感知中最基本的问题之一是求解欠定线性方程组。虽然这个问题看起来相当困难，但某些11 -优化算法似乎非常成功地解决了这个问题。最近的工作[14,28]严格证明（在大维度和统计背景下），如果系统中的方程数量（压缩感知术语中的测量）与未知向量的长度成正比，那么存在稀疏性（未知向量的非零元素的数量）也与未知向量的长度成正比，使得11 -优化算法成功地解决了系统。在最近的论文[78,81]中，我们考虑了所谓的块稀疏未知向量的设置。在大维度和统计上下文中，我们确定了任何给定数量（与未知向量的长度成正比）方程的允许稀疏性值的尖锐下界，以便l2/l1优化算法成功地求解该系统。[78,81]中建立的结果假设块稀疏向量的块长度相当大。本文将块长度作为系统的一个参数。因此，我们随后建立了作为块长度函数的允许块稀疏度值的明确下界。
One of the most basic problems in compressed sensing is solving an under-determined system of linear equations. Although this problem seems rather hard certain l1-optimization algorithm appears to be very successful in solving it. The recent work of [14, 28] rigorously proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that l1-optimization algorithm succeeds in solving the system. In more recent papers [78,81] we considered the setup of the so-called block-sparse unknown vectors. In a large dimensional and statistical context, we determined sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations such that an l2/l1-optimization algorithm succeeds in solving the system. The results established in [78, 81] assumed a fairly large block-length of the block-sparse vectors. In this paper we consider the block-length to be a parameter of the system. Consequently, we then establish sharp lower bounds on the values of the allowable block-sparsity as functions of the block-length.