Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices
Authors: Zengfeng Huang
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we almost settle the time complexity of this problem. In particular, we provide new space-optimal algorithms with faster running times. Moreover, we also show that the running times of our algorithms are near-optimal unless the state-of-the-art running time of matrix multiplication can be improved significantly. We provide new space-optimal algorithms with improved running time. We also prove that our running times cannot be significantly improved unless the state-of-the-art matrix multiplication algorithms can. Thus, we almost settle the time complexity of this problem. |
| Researcher Affiliation | Academia | Zengfeng Huang 1 School of Data Science, Fudan University, China. Correspondence to: Zengfeng Huang <huangzf@fudan.edu.cn>. |
| Pseudocode | Yes | Algorithm 1 Dense Shrink, Algorithm 2 Dense Shrink R, Algorithm 3 FDShrink, Algorithm 4 FFDdense, Algorithm 5 FFDsparse |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | This paper is theoretical and focuses on algorithm design and complexity analysis. It does not use specific publicly available datasets for empirical evaluation. The input is described as a large matrix A R^n d, but no concrete dataset name or access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments on datasets; therefore, it does not provide information about training/validation/test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity, not empirical execution. Therefore, no hardware specifications for experiments are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not mention any specific software dependencies or version numbers needed to replicate the work. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis, rather than empirical experiments. As such, it does not provide details about experimental setup, hyperparameters, or training settings. |