1292 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 4, APRIL 2006
The asymptotic properties of the left-hand side have been de-
termined by Garnaev and Gluskin [9]. This follows major work
by Kashin [10], who developed a slightly weaker version of this
result in the course of determining the Kolmogorov
-widths of
Sobolev spaces. See the original papers, or Pinkus’s book [8]
for more details.
Theorem 4: (Kashin, Garnaev, and Gluskin (KGG)) For
all
and
Theorem 1 now follows in the case by applying KGG
with the duality formula (I.6) and the equivalence formula (I.4).
The case
of Theorem 1 does not allow use of duality
and the whole range
is approached differently in this
paper.
E. Mysteries …
Because of the indirect manner by which the KGG result im-
plies Theorem 1, we really do not learn much about the phenom-
enon of interest in this way. The arguments of Kashin, Garnaev,
and Gluskin show that there exist near-optimal
-dimensional
subspaces for the Kolmogorov widths; they arise as the null
spaces of certain matrices with entries
which are known to
exist by counting the number of matrices lacking certain prop-
erties, the total number of matrices with
entries, and com-
paring. The interpretability of this approach is limited.
The implicitness of the information operator is matched
by the abstractness of the reconstruction algorithm. Based on
OR/IBC theory we know that the so-called central algorithm
is optimal. This “algorithm” asks us to consider, for given
information
, the collection of all objects which
could have given rise to the data
Defining now the center of a set
center
the central algorithm is
center
and it obeys, when the information is optimal,
see Section III below.
This abstract viewpoint unfortunately does not translate into
a practical approach (at least in the case of the
,
). The set is a section of the ball
, and finding the center of this section does not corre-
spond to a standard tractable computational problem. Moreover,
this assumes we know
and , which would typically not be
the case.
F. Results
Our paper develops two main types of results.
• Near-Optimal Information. We directly consider the
problem of near-optimal subspaces for Gel’fand
-widths
of
, and introduce three structural conditions
(CS1–CS3) on an
-by- matrix which imply that its
nullspace is near-optimal. We show that the vast majority
of
-subspaces of
are near-optimal, and random
sampling yields near-optimal information operators with
overwhelmingly high probability.
• Near-Optimal Algorithm. We study a simple nonlinear re-
construction algorithm: simply minimize the
norm of
the coefficients
subject to satisfying the measurements.
This has been studied in the signal processing literature
under the name Basis Pursuit; it can be computed by linear
programming. We show that this method gives near-op-
timal results for all
.
In short, we provide a large supply of near-optimal infor-
mation operators and a near-optimal reconstruction procedure
based on linear programming, which, perhaps unexpectedly,
works even for the nonconvex case
.
For a taste of the type of result we obtain, consider a specific
information/algorithm combination.
• CS Information. Let
be an matrix generated by
randomly sampling the columns, with different columns
independent and identically distributed (i.i.d.) random
uniform on
. With overwhelming probability for
large
, has properties CS1–CS3 discussed in detail
in Section II-A below; assume we have achieved such a
favorable draw. Let
be the basis matrix with
basis vector
as the th column. The CS Information
operator
is the matrix .
•
-minimization. To reconstruct from CS Information, we
solve the convex optimization problem
subject to
In words, we look for the object having coefficients
with smallest
norm that is consistent with the informa-
tion
.
To evaluate the quality of an information operator
, set
To evaluate the quality of a combined algorithm/information
pair
, set
Theorem 5: Let , be a sequence of problem sizes
obeying
, , ; and let be a
corresponding sequence of operators deriving from CS matrices
with underlying parameters
and (see Section II below). Let
. There exists so that
is near-optimal:
剩余17页未读，继续阅读
cyycxx100
- 粉丝: 5
- 资源: 19
我的内容管理
展开
最新资源
- 深入理解23种设计模式
- 制作与调试：声控开关电路详解
- 腾讯2008年软件开发笔试题解析
- WebService开发指南：从入门到精通
- 栈数据结构实现的密码设置算法
- 提升逻辑与英语能力：揭秘IBM笔试核心词汇及题型
- SOPC技术探索：理论与实践
- 计算图中节点介数中心性的函数
- 电子元器件详解：电阻、电容、电感与传感器
- MIT经典：统计自然语言处理基础
- CMD命令大全详解与实用指南
- 数据结构复习重点：逻辑结构与存储结构
- ACM算法必读书籍推荐：权威指南与实战解析
- Ubuntu命令行与终端：从Shell到rxvt-unicode
- 深入理解VC_MFC编程：窗口、类、消息处理与绘图
- AT89S52单片机实现的温湿度智能检测与控制系统
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
