Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization
Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization
复制标题
DOI：
10.1073/pnas.0437847100
复制
发表时间：
2003-03-04
影响因子：
11.1
通讯作者：
Elad, M
中科院分区：
文献类型：
--
作者：
Donoho, DL;Elad, M
给定向量d（k）的字典D = {d（k）），我们试图将信号S表示为具有标量系数gamma（k）的线性组合S = Sigma（k）gamma（k）d（k）。特别地，我们的目标是尽可能的稀疏表示。一般来说，这需要一个组合优化过程。以前的工作考虑了特殊情况，其中D是一个过完备系统，恰好由两个正交基组成，并表明，在两个基互不相干的条件下，假设S具有足够稀疏的表示，这种表示是唯一的，可以通过求解凸优化问题来找到：具体地说，最小化系数γ的l（1）范数。在这篇文章中，我们在一个更一般的设置，字典D可以产生于两个或几个基地，框架，甚至更少的结构化系统中获得平行的结果。我们简述三个应用：分离三维数据中的线性特征和平面特征，非合作多用户编码，以及过完备独立分量模型的识别。
Given a dictionary D = {d(k)) of vectors d(k), we seek to represent a signal S as a linear combination S = Sigma(k) gamma(k)d(k), with scalar coefficients gamma(k). in particular, we aim for the sparsest representation possible. In general, this requires a combinatorial optimization process. Previous work considered the special case where D is an overcomplete system consisting of exactly two orthobases and has shown that, under a condition of mutual incoherence of the two bases, and assuming that S has a sufficiently sparse representation, this representation is unique and can be found by solving a convex optimization problem: specifically, minimizing the l(1) norm of the coefficients gamma. In this article, we obtain parallel results in a more general setting, where the dictionary D can arise from two or several bases, frames, or even less structured systems. We sketch three applications: separating linear features from planar ones in 3D data, noncooperative multiuser encoding, and identification of over-complete independent component models.