L1范数优化与L2约束的近似线性关系分析
139 浏览量
更新于2024-08-28
收藏 741KB PDF 举报
"该研究论文探讨了L1范数目标函数值与L2范数约束界限之间的近似线性关系。"
在优化问题中，当目标函数是L1范数，并受到L2范数不等式约束时，这篇由Zhijing Yang、Bingo Wing-Kuen Ling和Chris Bingham共同完成的研究指出，存在一个近似的线性关联性。这个关系通过随机数据和现实世界的工业数据得到了验证。具体来说，这种关系有以下两个主要应用：
1. 估算L1范数目标函数值：无需数值求解优化问题，研究人员和工程师可以利用这种近似线性关系来估算目标函数的值。这对于那些计算复杂度高或需要快速预估结果的情况特别有用，因为直接求解优化问题可能耗时且资源密集。
2. 定义L2范数约束：此关系为定义L2范数的边界提供了洞见。一个简单的办法是，根据预期的目标函数值，利用这种线性关系来设定合适的约束范围。这样可以帮助设计者在满足性能要求的同时，避免过于保守或过于宽松的约束设置。
文章进一步详细讨论了这种线性关系的数学基础，可能包括拟合模型的建立、误差分析以及不同数据集下的表现。此外，作者可能还探讨了如何将这种方法应用于实际问题，如信号处理、机器学习中的稀疏表示或者工程优化设计等领域。
通过这种关系，优化问题的解决策略可能会有所改变。例如，在优化算法的设计中，可以先用近似方法快速确定搜索空间，然后在该范围内进行精细化的迭代。这不仅提高了效率，还可能改善算法的全局收敛性。
这项工作对于理解L1范数和L2范数约束之间的关系具有重要意义，对于优化问题的理论研究和实际应用都有一定的指导价值。它提供了一种新的工具，用于简化处理带有L1范数目标函数的复杂优化问题，特别是在需要快速决策和资源有限的情况下。
Since there are many inverse operators in Appendix 1, it requires
to study the invertibility of these matrices. The analysis is shown in
Appendix 2.
To verify the approximate linear relationship between ||x
∗
1
||
1
and
ɛ, many test pairs of A and y are generated. After performing these
tests, it is found that the approximate linear relationship between
||x
∗
1
||
1
and ɛ is valid for all these pairs of A and y. Only three
types of experiments are presented below to support the proposed
assertions because of the page limit.
2.1 Experiment 1: Signals satisfying the condition in (3)
Here, the relationship between ||x
∗
1
||
1
and ɛ when the condition in (3)
is satisfied is investigated. In this experiment, m = 40 and n = 100.
All the elements of A are independently drawn from a zero mean
Gaussian distribution. Then,
A
i
for i =1,…,100 is further
normalised to a unit energy vector. There are five non-zero
elements in α
0
and the locations of these elements are selected
randomly with their polarities also being chosen randomly. The
amplitude of the smallest non-zero element of α
0
is set to 0.2 and
the amplitudes of other elements are set to 1. Using this α
0
, y is
obtained. Obviously, x
∗
0
=
a
0
. x
∗
0
is shown in Fig. 1a.When ɛ =0,
||y||
2
/20, ||y||
2
/10 and 3||y||
2
/20, the corresponding x
∗
1
are shown
in Figs. 1b–e, respectively. It is shown in [7] that x
∗
0
= x
∗
1
when
ρ ≤ (1/5). This can also be verified from Figs. 1a–b. Although a
large value of ɛ allows a large bound on ||Ax
∗
1
− y||
2
, it results to a
small value of ||x
∗
1
||
1
. In other words, we have a high scarcity of
x
∗
1
. It can be seen in Fig. 1e that the total number of the non-zero
elements in x
∗
1
is 4 when ɛ = 3||y||
2
/20. This further demonstrates
the reason for the relaxation on the L
2
norm specification.
To further investigate the relationship between ||x
∗
1
||
1
and ɛ, 100
test pairs of A and y are generated as described in the above. For
each test pair of A and y, various values of ɛ, denoted as ɛ
i
, are
obtained via uniformly sampling in the range [0,||y||
2
]. Denote the
corresponding solution of (4) as x
∗
1
i
for i =1, 2, …, N. It is found
that an approximate linear relationship exists between ||x
∗
1
i
||
1
and
ɛ
i
for all these 100 test pairs of A and y. For an illustration
purpose, (1
i
, ||x
∗
1
i
||
1
) of one of the test pairs of A and y are shown
in Fig. 2. A straight line linear regression fitof(1
i
, ||x
∗
1
i
||
1
)
denoted as f (ɛ
i
)=k*ɛ
i
+ b* is also shown in Fig. 2. The relative L
2
norm error is defined as
N
i=1
|f (1
i
) −||x
∗
1
i
||
1
|
2
N
i=1
(||x
∗
1
i
||
1
)
2
. (5)
It is found that the L
2
norm error is around 2.3%. On the other hand,
it is also found that an approximate linear relationship exists between
x
∗
1
i
− x
∗
0
2
( x
∗
1
i
− x
∗
0
2
is the root mean squares error between x
∗
1
i
and x
∗
0
) and ɛ
i
for all these 100 test pairs of A and y. For an
illustration purpose, (1
i
, x
∗
1
i
− x
∗
0
2
) of one of the test pairs of A
and y are shown in Fig. 3. A linear regression fitof
(1
i
, x
∗
1
i
− x
∗
0
2
) denoted as g(1
i
) =
k
∗
1
i
+
b
∗
is also shown in
Fig. 3. The relative L
2
norm error is defined as
N
i=1
|g(1
i
) −||x
∗
1
i
||
1
|
2
N
i=1
(||x
∗
1
i
||
1
)
2
. (6)
It is found that the relative L
2
norm error is around 1.8%. All these
100 test pairs of A and y show similar results.
2.2 Experiment 2: Trials using randomly generated data
Since condition in (3) is difficult to satisfy in many practical
situations, x
∗
0
= x
∗
1
only happens in ideal scenarios. It is therefore
Fig. 1 Amplitude of the smallest non-zero element of α
0
is set to 0.2 and the amplitudes of other elements are set to 1
ax
∗
0
b–ex
∗
1
for ɛ =0,||y||
2
/20, ||y||
2
/10 and 3||y||
2
/20, respectively
IET Signal Process., 2015, Vol. 9, Iss. 9, pp. 670–680
672
&
The Institution of Engineering and Technology 2015
剩余10页未读，继续阅读
2022-07-14 上传
2019-03-18 上传
2021-04-22 上传
2021-05-24 上传
2021-05-26 上传
2021-04-22 上传
2021-10-11 上传
2021-09-30 上传
2021-05-22 上传
weixin_38638004
- 粉丝: 3
- 资源: 900
我的内容管理
展开
最新资源
- 深入浅出：自定义 Grunt 任务的实践指南
- 网络物理突变工具的多点路径规划实现与分析
- multifeed: 实现多作者间的超核心共享与同步技术
- C++商品交易系统实习项目详细要求
- macOS系统Python模块whl包安装教程
- 掌握fullstackJS：构建React框架与快速开发应用
- React-Purify: 实现React组件纯净方法的工具介绍
- deck.js：构建现代HTML演示的JavaScript库
- nunn：现代C++17实现的机器学习库开源项目
- Python安装包 Acquisition-4.12-cp35-cp35m-win_amd64.whl.zip 使用说明
- Amaranthus-tuberculatus基因组分析脚本集
- Ubuntu 12.04下Realtek RTL8821AE驱动的向后移植指南
- 掌握Jest环境下的最新jsdom功能
- CAGI Toolkit：开源Asterisk PBX的AGI应用开发
- MyDropDemo: 体验QGraphicsView的拖放功能
- 远程FPGA平台上的Quartus II17.1 LCD色块闪烁现象解析
