Unified View of Matrix Completion under General Structural Constraints
Authors: Suriya Gunasekar, Arindam Banerjee, Joydeep Ghosh
NeurIPS 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we present a unified analysis of matrix completion under general low-dimensional structural constraints induced by any norm regularization. We consider two estimators for the general problem of structured matrix completion, and provide unified upper bounds on the sample complexity and the estimation error. Our analysis relies on generic chaining, and we establish two intermediate results of independent interest: (a) in characterizing the size or complexity of low dimensional subsets in high dimensional ambient space, a certain partial complexity measure encountered in the analysis of matrix completion problems is characterized in terms of a well understood complexity measure of Gaussian widths, and (b) it is shown that a form of restricted strong convexity holds for matrix completion problems under general norm regularization. Further, we provide several non-trivial examples of structures included in our framework, notably including the recently proposed spectral k-support norm. |
| Researcher Affiliation | Academia | Suriya Gunasekar UT at Austin, USA suriya@utexas.edu Arindam Banerjee UMN Twin Cities, USA banerjee@cs.umn.edu Joydeep Ghosh UT at Austin, USA ghosh@ece.utexas.edu |
| Pseudocode | No | The paper defines mathematical estimators but does not present any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statements about releasing open-source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using a specific dataset. It defines a 'Uniform Sampling' model for theoretical analysis but does not refer to a concrete dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not report any software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |