Greed is Good: Algorithmic Results for Sparse Approximation

匹配追踪 稀疏逼近 基本追求 一般化 连贯性(哲学赌博策略) 贪婪算法 近似算法 算法 计算机科学 信号(编程语言) 代表(政治) 压缩传感 数学 信号处理 信号重构 统计 数学分析 电信 雷达 政治 政治学 法学 程序设计语言
作者
Joel A. Tropp
出处
期刊:IEEE Transactions on Information Theory [Institute of Electrical and Electronics Engineers]
卷期号:50 (10): 2231-2242 被引量:3721
标识
DOI:10.1109/tit.2004.834793
摘要

This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries. It provides a sufficient condition under which both OMP and Donoho's basis pursuit (BP) paradigm can recover the optimal representation of an exactly sparse signal. It leverages this theory to show that both OMP and BP succeed for every sparse input signal from a wide class of dictionaries. These quasi-incoherent dictionaries offer a natural generalization of incoherent dictionaries, and the cumulative coherence function is introduced to quantify the level of incoherence. This analysis unifies all the recent results on BP and extends them to OMP. Furthermore, the paper develops a sufficient condition under which OMP can identify atoms from an optimal approximation of a nonsparse signal. From there, it argues that OMP is an approximation algorithm for the sparse problem over a quasi-incoherent dictionary. That is, for every input signal, OMP calculates a sparse approximant whose error is only a small factor worse than the minimal error that can be attained with the same number of terms.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
无花果的应助被zmang采纳,获得10
1秒前
2秒前
3秒前
pipa_lemon完成签到,获得积分10
3秒前
彭于晏的应助被XiongJiuJiu采纳,获得10
3秒前
欢呼蓝天完成签到,获得积分10
4秒前
Tao发布了新的文献求助10
5秒前
柳七完成签到,获得积分10
5秒前
5秒前
7秒前
7秒前
可爱的函函的应助被风起采纳,获得10
8秒前
Mary发布了新的文献求助10
8秒前
8秒前
9秒前
9秒前
9秒前
JamesPei的应助被5420采纳,获得10
9秒前
吉路完成签到,获得积分10
11秒前
优美松思完成签到,获得积分10
12秒前
kadqcc发布了新的文献求助10
12秒前
苯环发布了新的文献求助10
13秒前
13秒前
永远的车神完成签到,获得积分10
13秒前
科目三的应助被小韩采纳,获得10
13秒前
14秒前
山高完成签到,获得积分10
14秒前
347u完成签到 ,获得积分10
14秒前
WR发布了新的文献求助10
14秒前
14秒前
听闻韬声依旧完成签到 ,获得积分10
15秒前
王乐乐发布了新的文献求助30
15秒前
15秒前
guoguo1119完成签到 ,获得积分10
16秒前
思源的应助被Li采纳,获得10
17秒前
66发发布了新的文献求助10
17秒前
lawang发布了新的文献求助10
17秒前
翟煜发布了新的文献求助10
17秒前
小蘑菇的应助被干净涵梅采纳,获得20
17秒前
今后的应助被ZhiHaoL采纳,获得10
17秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 2000
Agyptische Geschichte der 21.30. Dynastie 510
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
基于界面调控的高效湿气发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8192141
求助须知:如何正确求助?哪些是违规求助? 9578771
关于积分的说明 21861764
捐赠科研通 7791657
什么是DOI,文献DOI怎么找? 3436846
关于科研通互助平台的介绍 2560547
邀请新用户注册赠送积分活动 2483605