Noisy Low Rank Column-wise Sensing
This letter studies the AltGDmin algorithm for solving the noisy low rank column-wise sensing (LRCS) problem. Our sample complexity guarantee improves upon the best existing one by a factor $\max(r, \log(1/\epsilon))/r$ where $r$ is the rank of the unknown matrix and $\epsilon$ is the final desired accuracy. A second contribution of this work is a detailed comparison of guarantees from all work that studies the exact same mathematical problem as LRCS, but refers to it by different names.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Fast Algorithm for Low Rank + Sparse column-wise Compressive Sensing
This paper focuses studies the following low rank + sparse (LR+S) column-wise compressive sensing problem. We aim to recover an $n \times q$ matrix, $\X^* =[ \x_1^*, \x_2^*, \cdots , \x_q^*]$ from $m$ independent linear …
Compressive SensingIdentifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
This paper examines the problem of locating outlier columns in a large, otherwise low-rank, matrix. We propose a simple two-step adaptive sensing and inference approach and establish theoretical guarantees for its perfor…
Collaborative FilteringByzantine-Resilient Federated PCA and Low Rank Column-wise Sensing
This work considers two related learning problems in a federated attack prone setting: federated principal components analysis (PCA) and federated low rank column-wise sensing (LRCS). The node attacks are assumed to be B…
HyperJoin: LLM-augmented Hypergraph Link Prediction for Joinable Table Discovery
As a pivotal task in data lake management, joinable table discovery has attracted widespread interest. While existing language model-based methods achieve remarkable performance by combining offline column representation…
Representation LearningLink PredictionAverage Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
We study the column subset selection problem with respect to the entrywise $\ell_1$-norm loss. It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $n^{\…