MATLAB

Question

में कुशल कम रैंक अपॉक्सिमेशन मैं फ्रैबेनियस मानदंड के तहत इष्टतम है जो एक मैट्रिक्स के लिए एक निम्न रैंक अनुमान की गणना करना चाहता हूं। ऐसा करने का छोटा तरीका मैट्रिक्स के एसवीडी अपघटन की गणना करना है, सबसे छोटे एकवचन मूल्यों को शून्य पर सेट करें और कारकों को गुणा करके निम्न रैंक मैट्रिक्स की गणना करें। MATLAB में ऐसा करने के लिए कोई आसान और अधिक प्रभावी तरीका है?

Answer 1

यदि आपका मैट्रिक्स स्पैस है, तो svds का उपयोग करें।

मान लीजिए कि यह स्पैस नहीं है लेकिन यह बड़ा है, आप तेजी से कम रैंक अनुमान के लिए यादृच्छिक अनुमानों का उपयोग कर सकते हैं।

एक tutorial से

:

एक इष्टतम कम रैंक सन्निकटन आसानी से ओ (MN^2 ) में एक की SVD का उपयोग कर की जा सकती है। यादृच्छिक अनुमानों का उपयोग करते हुए हम दिखाते हैं कि ओ (एमएन लॉग (एन)) में "लगभग इष्टतम" निम्न रैंक पप्रोक्सिमेशन को कैसे प्राप्त किया जाए। एक blog से

मैटलैब कोड:

clear 
% preparing the problem 
% trying to find a low approximation to A, an m x n matrix 
% where m >= n 
m = 1000; 
n = 900; 
%// first let's produce example A 
A = rand(m,n); 
% 
% beginning of the algorithm designed to find alow rank matrix of A 
% let us define that rank to be equal to k 
k = 50; 
% R is an m x l matrix drawn from a N(0,1) 
% where l is such that l > c log(n)/ epsilon^2 
% 
l = 100; 
% timing the random algorithm 
trand =cputime; 
R = randn(m,l); 
B = 1/sqrt(l)* R' * A; 
[a,s,b]=svd(B); 
Ak = A*b(:,1:k)*b(:,1:k)'; 
trandend = cputime-trand; 
% now timing the normal SVD algorithm 
tsvd = cputime; 
% doing it the normal SVD way 
[U,S,V] = svd(A,0); 
Aksvd= U(1:m,1:k)*S(1:k,1:k)*V(1:n,1:k)'; 
tsvdend = cputime -tsvd; 

इसके अलावा, svd की econ पैरामीटर याद है।

Answer 2

svds फ़ंक्शन का उपयोग करके आप एसवीडी के आधार पर निम्न-रैंक अनुमान को तेजी से गणना कर सकते हैं।

[U,S,V] = svds(A,r); %# only first r singular values are computed 

svdseigs का उपयोग करता विलक्षण मूल्यों का एक सबसेट गणना करने के लिए - यह बड़े, विरल मैट्रिक्स के लिए विशेष रूप से तेजी से हो जाएगा। दस्तावेज देखें; आप सहिष्णुता और पुनरावृत्तियों की अधिकतम संख्या निर्धारित कर सकते हैं या बड़े के बजाय छोटे एकवचन मूल्यों की गणना करना चुन सकते हैं।

मैंने सोचा था कि svds और eigssvd और घने मैट्रिक्स के लिए eig तुलना में तेजी से हो सकता है, लेकिन फिर मैं कुछ बेंच मार्किंग किया था। वे केवल बड़े मैट्रिक्स के लिए तेजी से कर रहे हैं जब पर्याप्त कुछ मूल्यों अनुरोध कर रहे हैं:

n  k  svds   svd   eigs   eig   comment 
10  1  4.6941e-03 8.8188e-05 2.8311e-03 7.1699e-05 random matrices 
100 1  8.9591e-03 7.5931e-03 4.7711e-03 1.5964e-02  (uniform dist) 
1000 1  3.6464e-01 1.8024e+00 3.9019e-02 3.4057e+00 
     2  1.7184e+00 1.8302e+00 2.3294e+00 3.4592e+00 
     3  1.4665e+00 1.8429e+00 2.3943e+00 3.5064e+00 
     4  1.5920e+00 1.8208e+00 1.0100e+00 3.4189e+00 
4000 1  7.5255e+00 8.5846e+01 5.1709e-01 1.2287e+02 
     2  3.8368e+01 8.6006e+01 1.0966e+02 1.2243e+02 
     3  4.1639e+01 8.4399e+01 6.0963e+01 1.2297e+02 
     4  4.2523e+01 8.4211e+01 8.3964e+01 1.2251e+02 


10  1  4.4501e-03 1.2028e-04 2.8001e-03 8.0108e-05 random pos. def. 
100 1  3.0927e-02 7.1261e-03 1.7364e-02 1.2342e-02 (uniform dist) 
1000 1  3.3647e+00 1.8096e+00 4.5111e-01 3.2644e+00 
     2  4.2939e+00 1.8379e+00 2.6098e+00 3.4405e+00 
     3  4.3249e+00 1.8245e+00 6.9845e-01 3.7606e+00 
     4  3.1962e+00 1.9782e+00 7.8082e-01 3.3626e+00 
4000 1  1.4272e+02 8.5545e+01 1.1795e+01 1.4214e+02 
     2  1.7096e+02 8.4905e+01 1.0411e+02 1.4322e+02 
     3  2.7061e+02 8.5045e+01 4.6654e+01 1.4283e+02 
     4  1.7161e+02 8.5358e+01 3.0066e+01 1.4262e+02 

आकार- n वर्ग मैट्रिक्स के साथ, k एकवचन/eigen मूल्यों और सेकंड में runtimes। मैंने स्टीव एडडिन्स 'timeit बेंचमार्किंग के लिए फ़ाइल एक्सचेंज फ़ंक्शन का उपयोग किया, जो ओवरहेड और रनटाइम भिन्नताओं के लिए खाता करने का प्रयास करता है।

svds और eigs तेज हैं यदि आप बहुत बड़े मैट्रिक्स से कुछ मान चाहते हैं। यह प्रश्न में मैट्रिक्स के गुणों पर भी निर्भर करता है (edit svds आपको कुछ विचार क्यों देना चाहिए)।