1040 LAURENT EL GHAOUI AND HERV
´
E LEBRET
In the preceding definition, the norm used for the perturbation bound is the Frobenius
norm. As will be seen, the worst-case residual is the same when the norm used is the
largest singular value norm.
3.1. Optimizing the worst-case residual. The following results yield a nu-
merically efficient algorithm for solving the RLS problem in the unstructured case.
Theorem 3.1. When ρ =1, the worst-case residual (1) is given by
r(A, b, x)=kAx − bk +
p
kxk
2
+1.
The problem of minimizing r(A, b, x) over x ∈ R
m
has a unique solution x
RLS
, referred
to as the RLS solution. This problem can be formulated as the SOCP
minimize λ subject to kAx − bk≤λ−τ,
x
1
≤ τ.(15)
Proof. Fix x ∈ R
m
. Using the triangle inequality, we have
r(A, b, x) ≤kAx − bk +
p
kxk
2
+1.(16)
Now choose ∆ = [∆A ∆b]as
[∆A ∆b]=
u
p
kxk
2
+1
x
T
1
, where u =
Ax − b
kAx − bk
if Ax 6= b,
any unit-norm vector otherwise.
Since ∆ is rank one, we have k∆k
F
= k∆k = 1. In addition, we have
k(A +∆A)x−(b+∆b)k=kAx − bk +
p
kxk
2
+1,
which implies that ∆ is a worst-case perturbation (for both the Frobenius and max-
imum singular value norms) and that equality always holds in (16). Finally, unicity
of the minimizer x follows from the strict convexity of the worst-case residual.
Using an interior-point primal-dual potential reduction method for solving the
unstructured RLS problem (15), the number of iterations is almost constant [46].
Furthermore, each iteration takes O((n + m)m
2
) operations. A rough summary of
this analysis is that the method has the same order of complexity as one singular
value decomposition (SVD) of A.
3.2. Analysis of the optimal solution. Using duality results for SOCPs, we
have the following theorem.
Theorem 3.2. When ρ =1, the (unique) solution x
RLS
to the RLS problem is
given by
x
RLS
=
(
(µI + A
T
A)
−1
A
T
b if µ
∆
=(λ−τ)/τ > 0,
A
†
b else,
(17)
where (λ, τ) are the (unique) optimal points for problem (15).
Proof. Using the results of section 2.1, we obtain that the problem dual to (15) is
maximize b
T
z − v subject to A
T
z + u =0, kzk≤1,
u
v
≤1.
剩余29页未读，继续阅读
Quant0xff
- 粉丝: 1w+
- 资源: 459
我的内容管理
展开
最新资源
- 最优条件下三次B样条小波边缘检测算子研究
- 深入解析：wav文件格式结构
- JIRA系统配置指南：代理与SSL设置
- 入门必备：电阻电容识别全解析
- U盘制作启动盘：详细教程解决无光驱装系统难题
- Eclipse快捷键大全：提升开发效率的必备秘籍
- C++ Primer Plus中文版：深入学习C++编程必备
- Eclipse常用快捷键汇总与操作指南
- JavaScript作用域解析与面向对象基础
- 软通动力Java笔试题解析
- 自定义标签配置与使用指南
- Android Intent深度解析：组件通信与广播机制
- 增强MyEclipse代码提示功能设置教程
- x86下VMware环境中Openwrt编译与LuCI集成指南
- S3C2440A嵌入式终端电源管理系统设计探讨
- Intel DTCP-IP技术在数字家庭中的内容保护
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
