奇异值分解
创新互联服务项目包括修文网站建设、修文网站制作、修文网页制作以及修文网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,修文网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到修文省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
定理:设A为m*n阶复矩阵,则存在m阶酉阵U和n阶酉阵V,使得:
A = U*S*V’
其中S=diag(σi,σ2,……,σr),σi0 (i=1,…,r),r=rank(A)。
推论:设A为m*n阶实矩阵,则存在m阶正交阵U和n阶正交阵V,使得
A = U*S*V’
其中S=diag(σi,σ2,……,σr),σi0 (i=1,…,r),r=rank(A)。
说明:
1、 奇异值分解非常有用,对于矩阵A(m*n),存在U(m*m),V(n*n),S(m*n),满足A = U*S*V’。U和V中分别是A的奇异向量,而S是A的奇异值。AA'的正交单位特征向量组成U,特征值组成S'S,A'A的正交单位特征向量组成V,特征值(与AA'相同)组成SS'。因此,奇异值分解和特征值问题紧密联系。
2、 奇异值分解提供了一些关于A的信息,例如非零奇异值的数目(S的阶数)和A的秩相同,一旦秩r确定,那么U的前r列构成了A的列向量空间的正交基。
matlab奇异值分解
函数 svd
格式 s = svd (A) %返回矩阵A的奇异值向量
[U,S,V] = svd(A) %返回一个与A同大小的对角矩阵S,两个酉矩阵U和V,且满足= U*S*V'。若A为m×n阵,则U为m×m阵,V为n×n阵。奇异值在S的对角线上,非负且按降序排列
[U1,S1,V1]=svd(X,0) %产生A的“经济型”分解,只计算出矩阵U的前n列和n×n阶的S。
说明:
1.“经济型”分解节省存储空间。
2. U*S*V'=U1*S1*V1'。
2 矩阵近似值
奇异值分解在统计中的主要应用为主成分分析(PCA),它是一种数据分析方法,用来找出大量数据中所隐含的“模式”,它可以用在模式识别,数据压缩等方面。PCA算法的作用是把数据集映射到低维空间中去。
数据集的特征值(在SVD中用奇异值表征)按照重要性排列,降维的过程就是舍弃不重要的特征向量的过程,而剩下的特征向量张成空间为降维后的空间。
3 应用
在很长时间内,奇异值分解都无法并行处理。(虽然 Google 早就有了MapReduce 等并行计算的工具,但是由于奇异值分解很难拆成不相关子运算,即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。)最近,Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法,这是 Google中国对世界的一个贡献。
/*
本程序在linux g++下编译通过
bool svd(vectorvectordouble A, int K, vectorvectordouble U, vectordouble S, vectorvectordouble V);
A: 输入待分解矩阵
K: 输入,取前K大奇异值及奇异向量
U[0],U[1],...,U[K-1]: 前K大奇异值对应的左奇异向量
S[0],S[1],...,S[K-1]: 前K大奇异值 S[0]=S[1]=...=S[K-1]
V[0],V[1],...,V[K-1]: 前K大奇异值对应的右奇异向量
*/
#include cmath
#include iostream
#include iomanip
#include cstdlib
#include cstring
#include fstream
#include vector
using namespace std;
const int MAX_ITER=100000;
const double eps=0.0000001;
double get_norm(double *x, int n){
double r=0;
for(int i=0;in;i++)
r+=x[i]*x[i];
return sqrt(r);
}
double normalize(double *x, int n){
double r=get_norm(x,n);
if(reps)
return 0;
for(int i=0;in;i++)
x[i]/=r;
return r;
}
inline double product(double*a, double *b,int n){
double r=0;
for(int i=0;in;i++)
r+=a[i]*b[i];
return r;
}
void orth(double *a, double *b, int n){//|a|=1
double r=product(a,b,n);
for(int i=0;in;i++)
b[i]-=r*a[i];
}
bool svd(vectorvectordouble A, int K, vectorvectordouble U, vectordouble S, vectorvectordouble V){
int M=A.size();
int N=A[0].size();
U.clear();
V.clear();
S.clear();
S.resize(K,0);
U.resize(K);
for(int i=0;iK;i++)
U[i].resize(M,0);
V.resize(K);
for(int i=0;iK;i++)
V[i].resize(N,0);
srand(time(0));
double *left_vector=new double[M];
double *next_left_vector=new double[M];
double *right_vector=new double[N];
double *next_right_vector=new double[N];
int col=0;
for(int col=0;colK;col++){
double diff=1;
double r=-1;
while(1){
for(int i=0;iM;i++)
left_vector[i]= (float)rand() / RAND_MAX;
if(normalize(left_vector, M)eps)
break;
}
for(int iter=0;diff=eps iterMAX_ITER;iter++){
memset(next_left_vector,0,sizeof(double)*M);
memset(next_right_vector,0,sizeof(double)*N);
for(int i=0;iM;i++)
for(int j=0;jN;j++)
next_right_vector[j]+=left_vector[i]*A[i][j];
r=normalize(next_right_vector,N);
if(reps) break;
for(int i=0;icol;i++)
orth(V[i][0],next_right_vector,N);
normalize(next_right_vector,N);
for(int i=0;iM;i++)
for(int j=0;jN;j++)
next_left_vector[i]+=next_right_vector[j]*A[i][j];
r=normalize(next_left_vector,M);
if(reps) break;
for(int i=0;icol;i++)
orth(U[i][0],next_left_vector,M);
normalize(next_left_vector,M);
diff=0;
for(int i=0;iM;i++){
double d=next_left_vector[i]-left_vector[i];
diff+=d*d;
}
memcpy(left_vector,next_left_vector,sizeof(double)*M);
memcpy(right_vector,next_right_vector,sizeof(double)*N);
}
if(r=eps){
S[col]=r;
memcpy((char *)U[col][0],left_vector,sizeof(double)*M);
memcpy((char *)V[col][0],right_vector,sizeof(double)*N);
}else{
coutrendl;
break;
}
}
delete [] next_left_vector;
delete [] next_right_vector;
delete [] left_vector;
delete [] right_vector;
return true;
}
void print(vectorvectordouble A){
}
int main(){
int m=10;
int n=8;
int k=5;
//分解一个10*8的矩阵A,求其前5个奇异值和奇异向量
srand(time(0));
vectorvectordouble A;
A.resize(m);
for(int i=0;im;i++){
A[i].resize(n);
for(int j=0;jn;j++)
A[i][j]=(float)rand()/RAND_MAX-0.5;
}
cout"A="endl;
for(int i=0;iA.size();i++){
for(int j=0;jA[i].size();j++){
coutsetw(12)A[i][j]' ';
}
coutendl;
}
coutendl;
vectorvectordouble U;
vectordouble S;
vectorvectordouble V;
svd(A,k,U,S,V);
cout"U="endl;
for(int i=0;iU[0].size();i++){
for(int j=0;jU.size();j++){
coutsetw(12)U[j][i]' ';
}
coutendl;
}
coutendl;
cout"S="endl;
for(int i=0;iS.size();i++){
coutsetw(7)S[i]' ';
}
coutendl;
cout"V="endl;
for(int i=0;iV[0].size();i++){
for(int j=0;jV.size();j++){
coutsetw(12)V[j][i]' ';
}
coutendl;
}
return 0;
}
C语言中,函数调用的一般形式为:
函数名(实际参数表)
对无参函数调用时则无实际参数表。实际参数表中的参数可以是常数、变量或其它构造类型数据及表达式。各实参之间用逗号分隔。
#includestdio.h
int fun(int x, int y); // 函数声明,如果函数写在被调用处之前,可以不用声明
void main()
{
int a=1, b=2, c;
c = fun(a, b); // 函数的调用,调用自定义函数fun,其中a,b为实际参数,传递给被调用函数的输入值
}
// 自定义函数fun
int fun(int x, int y) // 函数首部
{ // {}中的语言为函数体
return xy ? x : y; // 返回x和y中较大的一个数
}
扩展资料
C语言中不允许作嵌套的函数定义。因此各函数之间是平行的,不存在上一级函数和下一级函数的问题。但是C语言允许在一个函数的定义中出现对另一个函数的调用。
这样就出现了函数的嵌套调用。即在被调函数中又调用其它函数。这与其它语言的子程序嵌套的情形是类似的。其关系可表示如图。
图表示了两层嵌套的情形。其执行过程是:执行main函数中调用a函数的语句时,即转去执行a函数,在a函数中调用b 函数时,又转去执行b函数,b函数执行完毕返回a函数的断点继续执行,a函数执行完毕返回main函数的断点继续执行。
参考资料:函数调用_百度百科