Linear Systems and Eigenvalue Problems — Problem 35 (Regression in the $\ell_p$ norm)

Definitions and mathematical statement

Let $A\in{\mathbb{R}}^{n\times d}$, $b\in{\mathbb{R}}^n$, and $\Omega\in{\mathbb{R}}^{n\times k}$, where $n,d,k$ are positive integers. The source does not specify the range of $p$. Under the usual norm convention, for $v\in{\mathbb{R}}^m$, \[ \|v\|_{\ell_p}=\left(\sum_{i=1}^m |v_i|^p\right)^{1/p}\quad(1\le p<\infty), \qquad \|v\|_{\ell_\infty}=\max_{1\le i\le m}|v_i|. \] These definitions do not settle which values of $p$, including whether $p=\infty$, the source intends to include.

Define the optimal original residual and the set of sketch-and-solve solutions by \[ r_p(A,b)=\min_{x\in{\mathbb{R}}^d}\|Ax-b\|_{\ell_p}, \qquad S_p(A,b,\Omega)=\operatorname*{argmin}_{x\in{\mathbb{R}}^d} \|\Omega^\top Ax-\Omega^\top b\|_{\ell_p}. \] The original residual lies in ${\mathbb{R}}^n$, and the sketched residual lies in ${\mathbb{R}}^k$.

Problem. Formulate a generalization of the source's OSI property to $\ell_p$ regression that ensures constant-factor accuracy of the sketch-and-solve procedure: for a solution $\tilde x\in S_p(A,b,\Omega)$, the proposed property should imply \[ \|A\tilde x-b\|_{\ell_p}\le C\,r_p(A,b) \] for a constant $C\ge1$. In particular, when $r_p(A,b)=0$, this inequality requires $A\tilde x=b$.

The supplied record does not define OSI, specify the allowed dependence of $C$, or state whether the guarantee must hold for every sketched minimizer or for a specified selection rule. It also gives no distribution for $\Omega$, success probability, sketch-size requirement, or quantifier order governing whether a sketch must work for a fixed instance or uniformly over a class of instances. These aspects of the requested property remain unresolved; no particular generalization is asserted here.

Short English statement

Find an $\ell_p$ analogue of the source's OSI property that guarantees that solving the sketched regression problem produces a solution whose original residual is within a constant factor of optimal. The supplied record leaves OSI, the intended range of $p$, and several guarantee quantifiers unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $800526$, source problem code catalogue entry, titled "Linear Systems and Eigenvalue Problems --- Problem 35 (Regression in the $\ell_p$ norm)." The registry attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open. This is a supplied status label, not an independently verified mathematical or literature assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 35. Supplied source URL: https://arxiv.org/abs/2602.05394. Supplied attribution/context: "Regression in the $\ell_p$ norm."
• Supplied provenance: accessed 2026-10-16; extraction method arxiv_latex; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. These are supplied source-verification metadata; the reference and its contents were not independently checked for this draft.