More Like this

1. Sparse representation of vectors in lattices and semigroups

   https://doi.org/https://doi.org/10.1007/s10107-021-01657-8  

   Iskander Aliev, Gennadiy Averkov (January 2022, Mathematical programming)

   We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the ℓ0 ℓ 0 -norm of the vector. Our main results are new improved bounds on the minimal ℓ0 ℓ 0 -norm of solutions to systems 𝐴𝑥𝑥=𝑏𝑏 A x x = b b , where 𝐴∈ℤ𝑚×𝑛 A ∈ Z m × n , 𝑏𝑏∈ℤ𝑚 b b ∈ Z m and 𝑥𝑥 x x is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with ℓ0 ℓ 0 -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over ℝ R , to other subdomains such as ℤ Z . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables. 

   more » « less
2. Optimizing Sparsity over Lattices and Semigroups

   https://doi.org/10.1007/978-3-030-45771-6_4  

   Aliev, I. (April 2020, Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science)

   Bienstock, D. (Ed.)

   Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the ℓ0-norm. Our main results are improved bounds on the ℓ0-norm of sparse solutions to systems 𝐴𝑥=𝑏, where 𝐴∈ℤ𝑚×𝑛, 𝑏∈ℤ𝑚 and 𝑥 is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with ℓ0-norm satisfying the obtained bounds. 

   more » « less
3. Averages Along the Primes: Improving and Sparse Bounds

   https://doi.org/10.1515/conop-2020-0003  

   Han, Rui; Krause, Ben; Lacey, Michael T.; Yang, Fan (February 2020, Concrete Operators)

   Abstract Consider averages along the prime integers ℙ given by {\mathcal{A}_N}f(x) = {N^{ - 1}}\sum\limits_{p \in \mathbb{P}:p \le N} {(\log p)f(x - p).} These averages satisfy a uniform scale-free ℓ p -improving estimate. For all 1 < p < 2, there is a constant C p so that for all integer N and functions f supported on [0, N ], there holds {N^{ - 1/p'}}{\left\| {{\mathcal{A}_N}f} \right\|_{\ell p'}} \le {C_p}{N^{ - 1/p}}{\left\| f \right\|_{\ell p}}. The maximal function 𝒜 * f = sup N |𝒜 N f | satisfies ( p , p ) sparse bounds for all 1 < p < 2. The latter are the natural variants of the scale-free bounds. As a corollary, 𝒜 * is bounded on ℓ p ( w ), for all weights w in the Muckenhoupt 𝒜 p class. No prior weighted inequalities for 𝒜 * were known. 

   more » « less
4. On birational boundedness of foliated surfaces

   https://doi.org/10.1515/crelle-2020-0009  

   Hacon, Christopher D.; Langer, Adrian (January 2021, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract In this paper we prove a result on the effective generation of pluri-canonical linear systems on foliated surfaces of general type. Fix a function {P:\mathbb{Z}_{\geq 0}\to\mathbb{Z}} , then there exists an integer {N>0} such that if {(X,{\mathcal{F}})} is a canonical or nef model of a foliation of general type with Hilbert polynomial {\chi(X,{\mathcal{O}}_{X}(mK_{\mathcal{F}}))=P(m)} for all {m\in\mathbb{Z}_{\geq 0}} , then {|mK_{\mathcal{F}}|} defines a birational map for all {m\geq N} . On the way, we also prove a Grauert–Riemenschneider-type vanishing theorem for foliated surfaces with canonical singularities. 

   more » « less
5. Inference in high-dimensional linear regression via lattice basis reduction and integer relation detection

   https://doi.org/10.1109/TIT.2021.3113921  

   Gamarnik, D.; Kizildag, E.C.; Ilias Zadik, I. (January 2021, IEEE transactions on information theory)

   We consider the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector $$\beta^*\in\mathbb{R}^p$$ from its linear measurements, using a small number $$n$$ of samples. Unlike most of the literature, we make no sparsity assumption on $$\beta^*$$, but instead adopt a different regularization: In the noiseless setting, we assume $$\beta^*$$ consists of entries, which are either rational numbers with a common denominator $$Q\in\mathbb{Z}^+$$ (referred to as $Q-$$rationality); or irrational numbers taking values in a rationally independent set of bounded cardinality, known to learner; collectively called as the mixed-range assumption. Using a novel combination of the Partial Sum of Least Squares (PSLQ) integer relation detection, and the Lenstra-Lenstra-Lov\'asz (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a $$\beta^*\in\mathbb{R}^p$ enjoying the mixed-range assumption, from its linear measurements $$Y=X\beta^*\in\mathbb{R}^n$$ for a large class of distributions for the random entries of $$X$$, even with one measurement ($n=1$). In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a $$\beta^*\in\mathbb{R}^p$$ enjoying the $Q-$rationality property, from its noisy measurements $$Y=X\beta^*+W\in\mathbb{R}^n$$, even from a single sample ($n=1$). We further establish that for large $$Q$$, and normal noise, this algorithm tolerates information-theoretically optimal level of noise. We then apply these ideas to develop a polynomial-time, single-sample algorithm for the phase retrieval problem. Our methods address the single-sample ($n=1$) regime, where the sparsity-based methods such as the Least Absolute Shrinkage and Selection Operator (LASSO) and the Basis Pursuit are known to fail. Furthermore, our results also reveal algorithmic connections between the high-dimensional linear regression problem, and the integer relation detection, randomized subset-sum, and shortest vector problems. 

   more » « less