*,/46,1,/46,*,最小二乘解的存在唯一性,最小二乘解的数值方法,数值分析,16,最小二乘解的存在唯一性数值分析 16,x,x,1,x,2,x,m,f,(,x,),y,1,y,2,y,m,离散数据的直线拟合,求拟合函数,:,A,c=y,超定方程组,x x1 x2 ,x,x,1,x,2,x,m,f,(,x,),y,1,y,2,y,m,离散数据的多项式拟合,求拟合函数,:,超定方程组,x x1 x2 ,x,x,1,x,2,x,m,f,(,x,),y,1,y,2,y,m,离散数据的线性拟合,求拟合函数,:,超定方程组,x x1 x2 ,回顾,:,回顾:,最小二乘拟合问题研究包括,:,模型的选取,存在唯一性,最小二乘解的计算,最小二乘拟合问题研究包括:模型的选取存在唯一性最小二乘解的计,广义矩阵,(,Ax=b,统一的理论解释,),广义矩阵(Ax=b统一的理论解释),相容方程的解,定义,:,一个方程组称为相容方程,(consistent equation),若至少存在一个解能够严格满足该方程组。,定理,:,线性方程,Ax,=,b,是相容的当且仅当增广矩阵的秩等于矩阵,A,的秩,即,rank(,A,b,)=rank(,A,),。,定理,:,相容方程,Ax,=,b,对,y,不等于零有解,x,=,Gb,当且仅当,AGA=A,。,(,G,称为是,A,的广义逆,generalized inverse),相容方程的解定义:一个方程组称为相容方程(consiste,相容方程解的唯一性,是否存在某种意义下的唯一性,?,最小范数解,(minimum norm solution),:,定理,:,Gb,是相容矩阵的最小范数解当且仅当,AGA=A,(,GA,),H,=,GA,。,参考,:,张贤达,矩阵分析与应用,清华大学,相容方程解的唯一性是否存在某种意义下的唯一性?最小范数解(m,不相容方程解的存在性,不相容方程的最小二乘解总是存在的。,证明,:,即证明正规方程是相容方程。,rank(,A,T,A,b,)=rank(,A,T,A,),不相容方程解的存在性不相容方程的最小二乘解总是存在的。证明:,定理,如果矩阵,A,列满秩,则,A,T,A,可逆,。,定理,矩阵,A,列满秩时,最小二乘解唯一,x,=,(,A,T,A,),-1,A,T,b,。,定理 如果矩阵A 列满秩,则ATA可逆。定理 矩阵A列满,不相容方程解的唯一性,是否存在某种意义下的唯一性,?,最小范数最小二乘解,(minimum norm least squares solution),定理,:,Gb,是不相容矩阵的最小范数最小二乘解当且仅当,AGA=A,(,AG,),H,=,AG,GAG=G,(,GA,),H,=,GA,。,注释,:,最小范数最小二乘广义矩阵即,Moore-Penrose,矩阵。,不相容方程解的唯一性是否存在某种意义下的唯一性?最小范数最,总结,相容方程,矩阵可逆则解唯一,如果矩阵秩亏损的情形,则所有解,中有唯一的最小范数解。,不相容方程,首先最小二乘解一定存在,如果矩阵列满秩则最小二,乘解唯一,如果矩阵秩亏损的情形,所有最小二乘解有,唯一的最小范数最小二乘解。,总结相容方程 矩阵可逆则解唯一,如果矩阵秩亏损的情形,则,对于任意矩阵,Moore-Penrose,逆矩阵存在且唯一。,Matlab:pinv(Pseudoinverse),比较,back slash,和,pinv,的区别。,Xy,pinv(X),*,y,norm(Xy),norm(pinv(X),*,y),对于任意矩阵,Moore-Penrose逆矩阵存在且唯一。,参考文献,:,Sparse and Redundant Representations:,From Theory to Applications in Signal and Image Processing,参考文献:Sparse and Redundant Re,最小二乘拟合问题研究包括,:,模型的选取,存在唯一性,最小二乘解的计算,最小二乘拟合问题研究包括:模型的选取存在唯一性最小二乘解的计,为什么不直接求解正规方程,?,为什么不直接求解正规方程?,初等行变换不改变方程组的解,1.,交换矩阵第,i,行与第,j,行,2.,非零数,k,乘以矩阵第,i,行的每个元素,3.,矩阵第,i,行的每个元素的,k,倍加到第,j,行的对应元素,1.7500 0.7500,1.9500 0.9500,初等行变换不改变方程组的解1.交换矩阵第i行与第j行2.非,A,(,n,1),=,F,n-,1,F,n-,2,F,1,A,其中,F,k,为,Frobenius,矩阵。,A=F,1,-1,F,2,-1,F,n-,1,-1,A,(,n,1),直接方法,:,高斯消元法,L U,矩阵,LU,分解是高斯消元法的矩阵编码。,A(n 1)=Fn-1Fn-2F1 A,回顾,:,回顾:,回顾,:,正交矩阵乘向量,则向量,2,范数不变。,Q,T,Q=I,y=Qx,正交矩阵,Q,T,Q=QQ,T,=I,半正交矩阵,Q,T,Q=I,(,列正交,),或,QQ,T,=I,(,行正交,),回顾:正交矩阵乘向量,则向量2范数不变。QTQ=I,y,Gram-Schmidt,正交化,Gram-Schmidt正交化,Gram-Schmidt,正交化,Gram-Schmidt正交化,Gram-Schmidt,正交化的矩阵编码,u,1,u,2,u,n,是正交基向量,R,单位上三角矩阵,Gram-Schmidt正交化的矩阵编码u1,u2,un是,Gram-Schmidt,正交化,Gram-Schmidt正交化,Gram-Schmidt,正交化,Gram-Schmidt正交化,Gram-Schmidt,正交化的矩阵编码,q,1,q,2,q,n,是标准正交基向量,Q,正交矩阵,R,上三角矩阵,Matlab,命令,:qr,Gram-Schmidt正交化的矩阵编码q1,q2,qn是,矩阵的正交三角分解,:,A=QR,注释,:,经典的,Gram-Schmidt,过程数值稳定性不令人满意,一般将一系列,Householder,变换,(,正交变换,),作用于最小二乘问题。,QR,分解有两种版本,:,完全,QR,分解和精简,QR,分解。,矩阵的正交三角分解:A=QR注释:经典的Gram-Sc,A=2 4;3-5;1 2;,Q,R=qr(A);%,完整型,y=11 3 6;,x=R(Q*y);,norm(A*x-y),解法,1(,完整,QR,分解,),A=2 4;3-5;1 2;解法1(完整QR分解),解法,2(,精简,QR,分解,),Q,R=qr(A,0);%,精简型,x=R(Q*y);,norm(A*x-y),解法2(精简QR分解)Q,R=qr(A,0);%,完整和精简,QR,分解的比较,完整和精简QR分解的比较,Ab (,算法,QR,分解,具体实现,Household,变换,),Tools Basic Fitting,If A is an M-by-N matrix with M N or NM then X=AB is the solution in the least squares sense to the under-or overdetermined system of equations A*X=B.,Matlab,超定方程组求解,Matlab,拟合,GUI,Ab (算法QR分解,具体实现Household变换),Matlab,的多项式拟合命令,polyfit,和,polyval,调用格式,P=polyfit(X,Y,N),调用格式,Y=polyval(P,X),load census,plot(x,y,o),P=polyfit(x,y,2);,polyval(P,2010),截至,2010,年,4,月,1,日,美国居住人口总数为,308,745,538,Matlab的多项式拟合命令polyfit和polyval截,Matlab,的非线性拟合命令,非线性拟合,lsqnonlin,和,lsqcurvefit,x=0:.1:10;,y=,0.12,*exp(-,0.213,*x)+,0.54,*exp(-,0.17,*x).*sin(,1.23,*x);,f=inline(a(1)*exp(-a(2)*x)+a(3)*exp(-a(4)*x).*sin(a(5)*x),a,x);,a,res=lsqcurvefit(f,1,1,1,1,1,x,y),Matlab的非线性拟合命令非线性拟合 lsqnonlin,严格满足插值条件,vs,追求最小残差平方和,适定方程组求解,vs,最小二乘问题求解,寻找数据的规律,(,函数,),或者说是压缩数据,思考,:,插值与拟合的异同,严格满足插值条件 vs 追求最小残差平方和适定方程组求解 v,作业,题目,:,数据的挖掘,(,拟合或插值,),数据,+,挖掘,知其然,知其所以然,用其然,利其然,作业题目:数据的挖掘(拟合或插值)数据+挖掘知其然,知其,测试数据集,Statistical Reference Dataset(http:/www.itl.nist.gov/div898/strd/),测试数据集 Statistical Refe,例,1,饮料的定价策略,一家公司在,22,个近似相等大小的城市尝试销售一种新型的运动型饮料,售价,(,美元,),以及在城市中每周的销量如下表,:,如果每件产品的制造成本是,0.23,美元,公司如何设置全国统一售价,利润最大化,?,城市,售价,销量,/,周,1234567891011,0.590.800.950.450.790.990.900.650.790.690.79,39802200185061002100170020004200244033002300,城市,售价,销量,/,周,1213141516171819102122,0.491.090.950.790.650.450.600.890.790.990.85,6001190196027604330696041601990286019202160,例1 饮料的定价策略 一家公司在22个近似相,例,2,非诚勿扰攻略,例,3,微信,3,点定位的真与假,2012,年,11,月,4,日,一条微博称微信可以通过三点定位法确定使用者的位置,即记住自己的位置和与某人之间的距离,变换两次位置重新记录距离,以这三个点为圆心、距离为半径画圆,交点就是要找的人的位置,圆圈越多,位置越精确。,提示,:,非线性最小二乘问题,最速下降法或,Gauss-Newton,方法求解,例2 非诚勿扰攻略例3 微信3点定位的真与假 2,例,4,Google,街景技术关键部分,(,大型复杂的非线性最小二乘问题,),http:/google-opensource.blogspot.ca/2012/05/introducing-ceres-solver-nonlinear.html,例4Google街景技术关键部分(大型复杂的非线性最小二乘问,最小二乘拟合问题研究包括,:,模型的选取,(,解释为什么选这个模型,),存在唯一性,最小二乘解的计算,(,线性与非线性,),最小二乘拟合问题研究包括:模型的选取(解释为什么选这个模型),不同变形,不同变形,数学概念,1,秩亏缺,(rank deficient),矩阵,A,属于,R,m*n,如果,rank(,A,)=,m,(,n,),则称矩阵行满秩,如果,rank(,A,)=,n,(,m,),则称矩阵列满秩,如果,rank(,A,)min,m,n,则称矩阵秩亏缺,数学概念1秩亏缺(rank deficient),数学概念,2,如果函数,f,的,f,f,.,f,(k),存在且连续。,理论分析中总是假设观测数据是由给定的函数生成,(,假设函数的数学性态,),然后定量的刻画插值函数或者拟合函数的近似程度,。,C,k,函数类,数学概念2如果函数f 的f,f,.,f(k),数学概念,3,极值,(,th