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]
The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
Authors: Franz J.Kirรกly, Louis Theran, Ryota Tomioka
JMLR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Section 7 validates our algorithms on the Movie Lens data set and shows that the structural features identified by our theories predict completability and completability phase transitions in practice. |
| Researcher Affiliation | Academia | Franz J. Kiraly EMAIL Department of Statistical Science University College London London WC1E 6BT, United Kingdom and Mathematisches Forschungsinstitut Oberwolfach 77709 Oberwolfach-Walke, Germany Louis Theran EMAIL Aalto Science Institute and Department of Information and Computer Science Aalto University 02150 Espoo, Finland Ryota Tomioka EMAIL Toyota Technological Institute at Chicago 6045 S. Kenwood Ave. Chicago, Illinois 60637, USA |
| Pseudocode | Yes | Algorithm 1 Completable closure. Input: A set E E of observed positions. Output: The rank r completable closure clr(E). Algorithm 2 Generic stress rank. Input: Observed positions E E. Output: The generic stress rank ฯ(E) of E in rank r. Algorithm 3 Completion with circuits. Input: A set E E of observed positions. Output: Estimates for the entries clr(E) \ E Algorithm 4 Minor Closure((V, W, E), r) Inputs: bipartite graph (V, W, E), rank r. Outputs: completed matrix A and minor closure of E. Algorithm 5 Local completion/denoising of a single entry (k, โ). Input: A set E E of observed positions, the entry. Output: Estimate for Akโ Algorithm 6 Local completion/denoising of a single entry (k, โ) in a rank 1 matrix. Input: A set E E of observed positions, observation variances ฯ, the position (k, โ). Output: Estimate for Akโ Algorithm 7 Error prediction for a single entry (k, โ), rank one. Input: A set E E of observed positions, observation variances ฯ, the position (k, โ). Output: Estimate for the (log-)variance error of the estimate b Akโ Algorithm 8 Find AClique((V, W, E), d1, d2) Algorithm 9 Find Core((V, W, E), d1, d2) |
| Open Source Code | No | The text discusses the source code of a third-party tool or platform that the authors used, but does not provide their own implementation code. Specifically, the paper mentions: 'For nuclear norm minimization (e), we used the implementation of the algorithm in (Tomioka et al., 2010) which solves the minimization problem...' |
| Open Datasets | Yes | Group Lens. Movielens 100k data set. Available online at http://grouplens.org/datasets/ movielens/; as downloaded on November 27th 2012. |
| Dataset Splits | No | The paper refers to the 'Movie Lens 100k data set' but does not specify how it was split into training, validation, or test sets for experiments. For synthetic data, it mentions '10 random masks of size 50 50 with 200 entries sampled uniformly and a random (50 50) matrix of rank one,' but this describes mask generation, not standard dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details such as CPU, GPU models, or memory specifications used for running the experiments. |
| Software Dependencies | No | The paper mentions 'MATLAB randperm function' and 'the implementation of the algorithm in (Tomioka et al., 2010)' but does not provide specific version numbers for MATLAB or any other software libraries or solvers used. |
| Experiment Setup | Yes | For a quantitative analysis, we perform experiments to investigate how the expected number of completable entries is influenced by the number of known entries. In particular, Section 6.3 suggests that a phase transition between the state where only very few additional entries can be completed and the state where a large set of entries can be completed should take place at some point. Figure 2 shows that this is indeed the case when slowly increasing the number of known entries: first, the set of completable entries is roughly equal to the set of known entries, but then, a sudden phase transition occurs and the set of completable entries quickly reaches the set of all entries. Figure 3 shows phase transition curves of various conditions for 100 100 matrices at rank 3. We consider uniform sampling model here. More specifically, we generated random 100 100 masks with various number of edges by first randomly sampling the order of edges (using MATLAB randperm function) and adding 100 entries at a time from 100 to 6000 sequentially. In this way, we made sure to preserve the monotonicity of the properties considered here. This experiment was repeated 100 times and averaged to obtain estimates of success probabilities. To test reconstruction, we generated 10 random masks of size 50 50 with 200 entries sampled uniformly and a random (50 50) matrix of rank one. The multiplicative noise was chosen entry-wise independent, with variance ฯi = (i 1)/10 for each entry. |