Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
Authors: Shusen Wang, Zhihua Zhang, Tong Zhang
JMLR 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section we conduct several sets of illustrative experiments to show the effect of the U matrix. We compare the three methods with different settings of c and s. We do not compare with other kernel approximation methods for the reasons stated in Section 3.2.2. Let X = [x1, . . . , xn] be the d n data matrix, and K be the RBF kernel matrix with each entry computed by Kij = exp xi xj 2 2 2σ2 where σ is the scaling parameter. When comparing the kernel approximation error K CUCT 2 F , we set the scaling parameter σ in the following way. We let k = n/100 and define η = Kk 2 F K 2 F = Pk i=1 σ2 i (K) Pn i=1 σ2 i (K), which indicate the importance of the top one percent singular values of K. In general η grows with σ. We set σ such that η = 0.9 or 0.99. All the methods are implemented in MATLAB and run on a laptop with Intel i5 2.5GHz CUP and 8GB RAM. To compare the running time, we set MATLAB in the single thread mode. |
| Researcher Affiliation | Academia | Shusen Wang EMAIL Department of Statistics University of California at Berkeley Berkeley, CA 94720, USA Zhihua Zhang EMAIL School of Mathematical Sciences Peking University Beijing 100871, China Tong Zhang EMAIL Department of Statistics Rutgers University Piscataway, New Jersey 08854, USA |
| Pseudocode | Yes | Algorithm 1 The Fast SPSD Matrix Approximation Model. 1: Input: an n n symmetric matrix K and the number of selected columns or target dimension of projection c (< n). 2: Sketching: C = KP using an arbitrary n c sketching matrix P (not studied in this work); 3: Optional: replace C by any orthonormal bases of the columns of C; 4: Compute another n s sketching matrix S, e.g. the leverage score sampling in Algorithm 2; 5: Compute the sketches ST C Rs c and ST KS Rs s; 6: Compute Ufast = (ST C) (ST KS)(CT S) Rc c; 7: Output: C and Ufast such that K CUfast CT . |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or provide a link to a code repository. It mentions implementation in MATLAB for experiments but no access information. |
| Open Datasets | Yes | We conduct experiments on several datasets available at the LIBSVM site. The datasets are summarized in Table 6. In this set of experiments, we study the effect of the U matrices. We use two methods to form C Rn c: uniform sampling and the uniform+adaptive2 sampling (Wang et al., 2016); we fix c = n/100 . For our fast model, we use two kinds of sketching matrices S Rn s: uniform sampling and leverage score sampling; we vary s from 2c to 40c. We plot s n against the approximation error K CUCT 2 F / K 2 F in Figures 3 and 4. The Nystr om method and the prototype model are included for comparison. |
| Dataset Splits | Yes | For each dataset, we randomly sample n1 = 50%n data points for training and the rest 50%n for test. |
| Hardware Specification | Yes | All the methods are implemented in MATLAB and run on a laptop with Intel i5 2.5GHz CUP and 8GB RAM. |
| Software Dependencies | No | All the methods are implemented in MATLAB and run on a laptop with Intel i5 2.5GHz CUP and 8GB RAM. To compare the running time, we set MATLAB in the single thread mode. The paper only mentions "MATLAB" without specifying a version number. |
| Experiment Setup | Yes | We set σ such that η = 0.9 or 0.99. All the methods are implemented in MATLAB and run on a laptop with Intel i5 2.5GHz CUP and 8GB RAM. To compare the running time, we set MATLAB in the single thread mode. In this set of experiments, we test the generalization performance of the kernel approximation methods on classification tasks. The classification datasets are described in Table 7. For each dataset, we randomly sample n1 = 50%n data points for training and the rest 50%n for test. In this set of experiments, we set k = 3 and k = 10. We let K Rn1 n1 be the RBF kernel matrix of the training data and k(x) Rn1 be defined by [k(x)]i = exp x xi 2 2 2σ2 , where xi is the i-th training data point. In the training step, we approximately compute the top k eigenvalues and eigenvectors, and denote Λ Rk k and V Rn1 k. The feature vector (extracted by KPCA) of the i-th training data point is the i-th column of Λ 0.5 VT . In the test step, the feature vector of test data x is Λ 0.5 VT k(x). Then we put the training labels and training and test features into the MATLAB K-nearest-neighbor classifier knnclassify to classify the test data. We fix the number of nearest neighbors to be 10. |