This paper provides the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals lying in a scaled $\ell_1$ ball, which is a commonly adopted relaxation of the exactly $k$-sparse assumption. In prior works, the best known upper bounds on uniform Euclidean error are of order $\widetilde{O}((k/m)^{1/3})$, where $m$ is the number of measurements. Under sub-Gaussian matrices, we establish nearly matching lower bounds for both the canonical one-bit compressed sensing model and the uniformly dithered model. Our argument is to first embed a small Euclidean ball into the signal set, which is straightforward for the dithered model but relies on a lifting map for the canonical model, and then construct two signals in this small ball that are separated in Euclidean distance by at least $(k/m)^{1/3}$ (up to logarithmic factor) but are indistinguishable from the binary measurements. Moreover, our argument extends to approximately sparse signals that live in a properly scaled $\ell_q$ ball $(q\in [0,1])$, yielding a lower bound $\widetilde{\Omega}((k/m)^{\frac{2-q}{2+q}})$ that smoothly bridges the cases of exact sparsity ($q=0$) and $\ell_1$ sparsity ($q=1$). Finally, we discuss the extensions of our lower bounds to sub-Weibull matrices, adversarial bit flipping, matrix recovery, and characterize the transition to the non-sparse case.
A universal, sample-optimal convergence theorem for the original BIHT algorithm is proved and a scalar lower bound is proved showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely.
A mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing and a novel characterization of the distribution of signs in the Gram matrix is developed.
Michael I. Ivanitskiy, J. Jasper, Emily J. King et al.· 0 citations
Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/\epsilon))$ and two-point bound $O(d\epsilon^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,\epsilon^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $\Omega(\min\{d,\epsilon^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex objective with a universal Lipschitz scale over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let $T_\epsilon$ denote the minimum number of queries required to return an $\epsilon$-suboptimal point with probability at least $1/2$, uniformly over the function class. We prove that \[T_\epsilon\ge c\,\frac{d\min\{d,\epsilon^{-2}\}}{\log\!\bigl(\min\{d,\epsilon^{-2}\}\bigr)},\] for $d\ge d_0$ and $0<\epsilon\le\epsilon_0$, where $c,\epsilon_0>0$ and $d_0\in\mathbb N$ are universal constants. This gives $\Omega\left(\frac{d}{\epsilon^2\log(1/\epsilon)}\right)$ in the low-accuracy regime $\epsilon\ge d^{-1/2}$ and $\Omega\left(\frac{d^2}{\log d}\right)$ in the high-accuracy regime $\epsilon\le d^{-1/2}$ with the latter independent of $\epsilon$. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.
Haihan Zhang, Chenheng Zhang, Zhiquan Qi et al.· 0 citations
In this paper we focus on the stability of positive semidefinite matrix sensing maps $\Phi_{\mathcal{A}}(X)=(\langle A_i,X\rangle)_{i=1}^m$ where $A_i\succeq 0$, $X\succeq0$ and $\operatorname{rank}(X)\le r$. We introduce the bi-Lipschitz constants of $\Phi_{\mathcal{A}}(X)$ and define the global condition numbers as the ratio of upper and lower Lipschitz constants. We give deterministic universal lower bounds for these condition numbers, that depend only on the rank $r$ and on the underlying field. We then investigate the random rank-one Gaussian measurements and show that our lower bounds on condition numbers are asymptotically sharp, and therefore the random rank-one Gaussian measurements are asymptotically optimal. As an application, we derive the stability guarantees for an $\ell_1$-residual PhaseLift-type estimator at the optimal sampling scale.
In this work, we consider the problem of sparse signal recovery known as compressed sensing using $\ell_1$-minimization.
We show how the $\ell_1$-minimization problem (also known as basis pursuit) can be transformed into an equivalent linear programming (LP) problem, and provide a proof of the equivalence of these two problems.
We conduct an experimental comparison of modern solvers (Gurobi, HiGHS, CPLEX, and Clarabel) for solving the LP problem on test data generated according to theoretical recovery guarantees for matrices with normally distributed elements. The results show that the open-source solver Clarabel is a competitive alternative to proprietary solvers in terms of speed.
We also propose a method for verifying the uniqueness of the obtained solution using an auxiliary quadratic programming problem with a strictly convex objective function.
A geometric interpretation of the uniqueness conditions is provided, and the application of the method is demonstrated on an example of a matrix with integer elements.
Anastasiia O. Storozhenko, P. Stetsyuk· KyivAcademUs2026· 0 citations
Noise-shaped one-bit coefficients in normalized discrete polynomial Fourier extension are studied, and exact orthogonality identities, fourth-moment formulas, local kernel estimates, and oscillatory transfer bounds are established.
