Cover Image

Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Zhou, Fengqin
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sparse Linear Regression is Easy on Random Supports
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Robust Sparse Regression with Non-Isotropic Designs
by: Liu, Chih-Hung, et al.
Published: (2024)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

Sample-Efficient Linear Regression with Self-Selection Bias
by: Gaitonde, Jason, et al.
Published: (2024)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

Transductive and Learning-Augmented Online Regression
by: Raman, Vinod, et al.
Published: (2025)

Efficient and Provable Algorithms for Covariate Shift
by: Adil, Deeksha, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets
by: Bruch, Sebastian, et al.
Published: (2025)

Fast and Efficient Matching Algorithm with Deadline Instances
by: Song, Zhao, et al.
Published: (2023)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
by: Kalavasis, Alkis, et al.
Published: (2026)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
by: Zhu, Yanhui, et al.
Published: (2024)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
by: Diakonikolas, Ilias, et al.
Published: (2024)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
by: Wang, Jiachen T., et al.
Published: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
by: Rohatgi, Dhruv, et al.
Published: (2025)

A Competitive Algorithm for Agnostic Active Learning
by: Price, Eric, et al.
Published: (2023)

Linear Regression under Missing or Corrupted Coordinates
by: Diakonikolas, Ilias, et al.
Published: (2025)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
by: Lee, Russell, et al.
Published: (2022)

Kruskal-EDS: Edge Dynamic Stratification
by: Mercadier, Yves
Published: (2026)

Value-Compressed Sparse Column (VCSC): Sparse Matrix Storage for Redundant Data
by: Ruiter, Skyler, et al.
Published: (2023)

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
by: Dehghankar, Mohsen, et al.
Published: (2024)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

Linear Regression with Unknown Truncation Beyond Gaussian Features
by: Kouridakis, Alexandros, et al.
Published: (2026)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Batch List-Decodable Linear Regression via Higher Moments
by: Diakonikolas, Ilias, et al.
Published: (2025)

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
by: Diakonikolas, Ilias, et al.
Published: (2025)

Reweighted Solutions for Weighted Low Rank Approximation
by: Woodruff, David P., et al.
Published: (2024)

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
by: Agarwal, Arpit, et al.
Published: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

Infrequent Resolving Algorithm for Online Linear Programming
by: Li, Guokai, et al.
Published: (2024)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
by: Oettershagen, Lutz
Published: (2026)