# Subspace Embedding and Linear Regression with Orlicz Norm

arXiv: https://arxiv.org/abs/1806.06430 · HTML: https://mlsanity.com/paper/1806.06430/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2018.

## Built on by (most cited first, 19 of 19)

- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Fast Graph Neural Tangent Kernel via Kronecker Sketching](https://mlsanity.com/paper/2112.02446/) (2021)
- [Tailoring to the Tails: Risk Measures for Fine-Grained Tail Sensitivity](https://mlsanity.com/paper/2208.03066/) (2022)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)
- [Generalized Sobolev IPM for Graph-Based Measures](https://mlsanity.com/paper/2510.25591/) (2025)
- [Scaling Federated Linear Contextual Bandits via Sketching](https://mlsanity.com/paper/2605.00500/) (2026)
- [Online Algorithms via Minimax and Posterior Matching](https://mlsanity.com/paper/2608.01616/) (2026)
- [Efficient Linear Bandits via Cluster-Aware Sketching](https://mlsanity.com/paper/2609.27594/) (2026)

## Abstract (arXiv)

We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function G:ℝ_+rightarrowℝ_+ with G(0)=0: the Orlicz norm of a vector x∈ℝn is defined as  |x|G=infleftα>0largemidsumi=1n G(|xi|/α)≤ 1right.  We consider the cases where the function G(·) grows subquadratically. Our main result is based on a new oblivious embedding which embeds the column space of a given matrix A∈ℝn× d with Orlicz norm into a lower dimensional space with ℓ2 norm. Specifically, we show how to efficiently find an embedding matrix S∈ℝm× n,m<n such that forall x∈ℝd,Omega(1/(dlog n)) · |Ax|G≤ |SAx|2≤ O(d2log n) · |Ax|G. By applying this subspace embedding technique, we show an approximation algorithm for the regression problem minx∈ℝd |Ax-b|G, up to a O(dlog2 n) factor. As a further application of our techniques, we show how to also use them to improve on the algorithm for the ℓp low rank matrix approximation problem for 1≤ p<2.