Super-Resolution Off the Grid
Authors: Qingqing Huang, Sham M. Kakade
NeurIPS 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This work provides an algorithm with the following favorable guarantees: The algorithm uses Fourier measurements, whose frequencies are bounded by O(1/ ) (up to log factors). Previous algorithms require a cutoff frequency which may be as large as (d/ ). The number of measurements taken by and the computational complexity of our algorithm are bounded by a polynomial in both the number of points k and the dimension d, with no dependence on the separation . In contrast, previous algorithms depended inverse polynomially on the minimal separation and exponentially on the dimension for both of these quantities. Our estimation procedure itself is simple: we take random bandlimited measurements (as opposed to taking an exponential number of measurements on the hypergrid). Furthermore, our analysis and algorithm are elementary (based on concentration bounds for sampling and the singular value decomposition). |
| Researcher Affiliation | Academia | Qingqing Huang LIDS, qqh@mit.edu Sham M. Kakade University of Washington, Department of Statistics, Computer Science & Engineering, sham@cs.washington.edu |
| Pseudocode | Yes | Algorithm 1: General algorithm; Algorithm 2: Tensor Decomp |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository link, explicit statement of code release) for the source code of the described methodology. |
| Open Datasets | No | The paper describes a theoretical algorithm and analysis for signal recovery. It does not use or refer to any publicly available dataset in the traditional sense of machine learning datasets (e.g., CIFAR-10, ImageNet) for empirical evaluation. It refers to 'measurements' and 'samples' but these are theoretical constructs within the problem setup rather than external, accessible datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits (training, validation, test sets). |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run experiments. This is a theoretical paper focused on algorithm design and guarantees. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers needed to replicate the work. It mentions algorithms like 'Jennrich’s algorithm' but not as versioned software. |
| Experiment Setup | No | The paper is theoretical, presenting an algorithm and its guarantees. It does not describe an empirical experimental setup with hyperparameters or system-level training settings. |