...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Decoding by linear programming
【24h】

Decoding by linear programming

机译：线性编程解码

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.
机译：本文考虑具有实值输入/输出的自然纠错问题。我们希望从损坏的测量值y = Af + e中恢复输入向量f / spl isin / R / sup n /。在此，A是一个m×n（编码）矩阵，而e是一个任意且未知的错误向量。是否可以从数据y中准确恢复f？我们证明在编码矩阵A的适当条件下，输入f是/ spl lscr // sub 1 /最小化问题（/ spl par / x / spl par // sub / spl lscr / 1 / ：= / spl Sigma // sub i / | x / sub i / |）min（g / spl isin / R / sup n /）/ spl par / y-Ag / spl par // sub / spl lscr / 1 /如果错误向量的支持不是太大，则/ spl par / e / spl par // sub / spl lscr / 0 /：= | {i：e / sub i / / spl ne / 0} | / spl les // spl rho // spl middot / m表示一些/ spl rho /> 0。简而言之，可以通过解决一个简单的凸优化问题（可以将其重铸为线性程序）来精确地恢复f。另外，数值实验表明该恢复程序工作不合理。即使在很大一部分输出损坏的情况下，f仍可以准确恢复。这项工作与寻找线性方程组的未充分确定的稀疏解的问题有关。从高度不完整的测量中恢复信号的问题也存在着重大联系。实际上，本文介绍的结果改进了我们之前的工作。最后，/ spl lscr // sub 1 /成功的基础是至关重要的属性，我们称之为统一不确定性原则，我们将对其进行详细描述。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号