没有合适的资源?快使用搜索试试~ 我知道了~
LLL算法的分析和应用.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 113 浏览量
2022-07-10
22:15:48
上传
评论
收藏 3.56MB PDF 举报
温馨提示
试读
96页
LLL算法的分析和应用.pdf
资源推荐
资源详情
资源评论
中文摘要
摘要
在许多工程问题的应用中,会要求解整数最小二乘问题。LLL算法经常
被作为一种预条件使用。但是使用LLL的工程师一般对其如何具体作用并不
了解,Luk和Tracy[111具体描述了其实现的步骤,并且推导了一种新的实现
方法。Luk和Qiao[12]从数据的上溢和下溢角度,比较了原来的LLL算法和新
的LLL算法。在本篇文章中,我们首先对这两种算法在求解最小二乘问题中
的一些数值性质进行分析;然后再提出一种可以加快LLL算法速度的矩阵预处
理;最后对算法中参数的取值进行一些分析,并将QR分解和U。L算法整合在一
起。
关键词:LLL算法,整数最小二乘,球译码,空间点阵
中图法分类号:0241.6
引言
引言
自从Lenstra,Lenstra和Lovasz[1]提出LLL算法之后,其作为一种缩减点阵空
间(1attice
space)的算法,在很多领域都发挥了很大的作用,比如整数规划[4],
密码学[7】[8】,数论[9]等。螂Tracy[11】提出了一种新的实现方法,使LLL算
法更易于理解和使用。本文主要研究的,就是这种新的实现方法。
本文就由通信解码中,求解整数最小二乘问题的背景应用,引入LLL算
法,并对其进行研究和分析。主要的创新有:
1.对LLL算法的两种实现如何输出正交矩阵Q进行研究分析,并用数值实验
和理论分析对其性质进行考察
2.根据LLL算法的目的,对QR分解进行了一些改动,使其分解得到的上三角
矩阵R更容易被LLL算法缩减,相当于对矩阵进行预处理:
3.对LLL算法中的u的取值进行了研究,包括在效率和效果上的比较,以帮
助使用者确定其取值;
4.整合-fQR分解和LLL算法,推导了一般矩阵的LLL分解算法。
本文的章节安排如下:第一章比较完整地介绍了最小二乘问题的背景和求
解方法;第二章引入LLL算法,并介绍两种U工算法的具体实现;第三章在最
小二乘问题中应用LLL算法观察效果,并考察两种实现在计算正交矩阵Q时的
表现,进行数值实验以进行对比;第四章对LLL算法进行预处理,提出了修改
的QR分解,使LLL算法更容易进行;第五章则是先对LLL算法中的参数u进行分
析研究,之后设计一种一般矩阵的LLL分解算法,将QR分解与LLL算法整合在
一起;第六章为总结部分。
本文使用的记号约定如下:4表示一般的实矩阵,R是上三角矩阵,U是
单位上三角阵,D表示对角矩阵,Z和M表示单模阵。ei表示第i个分量为1,
其它分量都为0的方向列向量。A~(A)和Amin(A)分别表示矩阵A模长最长和最
短的特征值。另外,我们借用MATLAB语法来记一段整数范围:(k:n)表示
(k,k+1,…,n)。
一Ⅳ一
第一章整数最小二乘问题
这就是整数最d'---乘问题。当然,对于这种方法,我们也并不能保证得到的一
定就是原来的信号,但由于v是一个相对比较小的向量,因此我们仍可以期待其
有较高的正确率。
1。2整数最dx__--乘问题
考虑整数最d'--乘问题:
mi。n。Ilax—b眩
(1.2)
xEZ“‘
~’
、 。
其中A∈Rm黼,m≥礼,b∈R”.假设A为列满秩的矩阵。
/
/7
,,,,,7·易
//
/7
,
/
7-
,
,
●
-'
●
,
, ’
k
,
,
● ● ‘
■■
●
, ● ●
v
●
, , ,
, , ,
,
,
,
, , ,
, , ,
, , ,
一…一………一一-…………。一………
, , ,
, , ,
, , ,
,
, ,
, , ,
, , , ●
, , , ,
, ,
, ,
, ,
,
, , ,
, ,
…………7…………T…………7…
, , ,
/7
a1/
,,7 ,,7
,/
图1.2
整数最小二乘问题示意图(2维)
借助图形来表示,可以更直观地理解这个问题。也就是A的列为一组
基,x为整数,那么Ax也就是这组基的整数倍线性组合,组成了一个点阵空
间(1attice
space)的网格。图1.2是二维情况下的示意图,其中a1,a2分别表
示A的第--YU和第二列,需要求解的即是离b最近的网格点。
在一般的标准解法中,要利用正交变换不改变2.范数的性质,先用QR分解
将A约化成一个上三角矩阵
A=P
I苫I,
其中P是正交矩阵,R是上三角矩阵。根据R的维数,将P进行分块表示
为P=[P1,e2],其中P1是m
X几矩阵,这样我们就有
“Ax—b旧=||[苫]x-[P1
P2]wblI:=II脓-gll;+II霹b嚏,
其中6=pTb。这样,一个普通的整数最小二乘问题(1.2)就被简化成一个上三
一2一
剩余95页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功