svd演算法實現

A. 怎麼在推薦系統中使用svd演算法

SVD演算法 SVD演算法可用來求解大多數的線性最小二乘法問題. SVD 演算法基於如下分解定理:對任 意的矩陣 Am ×n ,當其行數 m 大於等於列數 n 時,可以分解為正交矩陣 Um ×n , 非負對角矩陣 Wn×n以及正交矩陣Vn×n的轉置的乘積,即 Am×n = Um×n ·[diag(

B. 關於MATLAB中稀疏表示的K-SVD演算法的疑問，跪求各位大神指點，感激不盡，詳細內容見問題補充

字典都是小數是因為裡面每個列都經過了normalization，L2 norm都是1
如果要得到稀疏系數，試試OMPerr

C. Matlab中求解矩陣（不一定是方陣）的演算法有哪些

iug uhg hkj;

D. Matlab 的 svd 是怎麼實現的

在MATLAB里打開svd的源碼可以看到只有一堆注釋，最後寫的是該函數為built-in function。事實上，MATLAB的矩陣計算使用的是Intel的MKL庫，這個庫基本是現有BLAS/LAPACK實現中最快的了。svd是LAPACK中的標准運算，因此MATLAB實際是使用的MKL庫來做svd。
MKL作為一個商業庫，其演算法細節和代碼是不公開的，而且業界對於這種基本演算法必然會有非常獨到的優化，涉及到大量細節（演算法本身的細節，以及代碼層次的細節）。svd的經典演算法有Golub-Kahan演算法、分治法、Jacobi法幾種，我推測MKL具體實現的是分治法。

E. 求SVD演算法的C++實現代碼

/** C++ function for SVD
函數原型:
bool svd(vector<vector<double> > A, int K, std::vector<std::vector<double> > &U, std::vector<double> &S, std::vector<std::vector<double> > &V);
其中
A是輸入矩陣，假設A的維數是m*n，那麼本函數將A分解為U diag(S) V'
其中U是m*K的列正交的矩陣. V是n*K的列正交矩陣，S是K維向量。K由第二個參數指定。
U的第i列是A的第i大奇異值對應的左歧義向量,S[i]=A的第 i大奇異值,V的第i列是A的第i大奇異值對應的右歧義響亮.
K是需要分解的rank，0<K<=min(m,n)

本程序採用的是最基本冪迭代演算法，在linux g++下編譯通過
**/


#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;i<n;i++)
r+=x[i]*x[i];
return sqrt(r);
}
double normalize(double *x, int n){
double r=get_norm(x,n);
if(r<eps)
return 0;
for(int i=0;i<n;i++)
x[i]/=r;
return r;
}

inline double proct(double*a, double *b,int n){
double r=0;
for(int i=0;i<n;i++)
r+=a[i]*b[i];
return r;
}
void orth(double *a, double *b, int n){//|a|=1
double r=proct(a,b,n);
for(int i=0;i<n;i++)
b[i]-=r*a[i];

}


bool svd(vector<vector<double> > A, int K, std::vector<std::vector<double> > &U, std::vector<double> &S, std::vector<std::vector<double> > &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;i<K;i++)
U[i].resize(M,0);
V.resize(K);
for(int i=0;i<K;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];
while(1){
for(int i=0;i<M;i++)
left_vector[i]= (float)rand() / RAND_MAX;
if(normalize(left_vector, M)>eps)
break;
}
int col=0;
for(int col=0;col<K;col++){
double diff=1;
double r=-1;
for(int iter=0;diff>=eps && iter<MAX_ITER;iter++){
memset(next_left_vector,0,sizeof(double)*M);
memset(next_right_vector,0,sizeof(double)*N);
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
next_right_vector[j]+=left_vector[i]*A[i][j];

r=normalize(next_right_vector,N);
if(r<eps) break;
for(int i=0;i<col;i++)
orth(&V[i][0],next_right_vector,N);
normalize(next_right_vector,N);

for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
next_left_vector[i]+=next_right_vector[j]*A[i][j];
r=normalize(next_left_vector,M);
if(r<eps) break;
for(int i=0;i<col;i++)
orth(&U[i][0],next_left_vector,M);
normalize(next_left_vector,M);
diff=0;
for(int i=0;i<M;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
break;
}
delete [] next_left_vector;
delete [] next_right_vector;
delete [] left_vector;
delete [] right_vector;

return true;
}

void print(vector<vector<double> > &A){
for(int i=0;i<A.size();i++){
for(int j=0;j<A[i].size();j++){
cout<<setprecision(3)<<A[i][j]<<' ';
}
cout<<endl;
}
}
int main(){
int m=10;
int n=5;
srand(time(0));
vector<vector<double> > A;
A.resize(m);

for(int i=0;i<m;i++){
A[i].resize(n);
for(int j=0;j<n;j++)
A[i][j]=(float)rand()/RAND_MAX;
}
print(A);
cout<<endl;

vector<vector<double> > U;
vector<double> S;
vector<vector<double> > V;
svd(A,2,U,S,V);
cout<<"U="<<endl;
print(U);
cout<<endl;
cout<<"S="<<endl;
for(int i=0;i<S.size();i++){
cout<<S[i]<<' ';
}
cout<<endl;
cout<<"V="<<endl;
print(V);
return 0;
}

F. 怎麼樣用matlab的svd演算法處理一個稀疏矩陣

確實有點大的 兩個指定頂點之間的最短路徑 問題如下：給出了一個連接若干個城鎮的鐵路網路，在這個網路的兩個指定城鎮間，找一條最短鐵路線。 以各城鎮為圖G的頂點，兩城鎮間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對 G的每一邊e...