An extremal problem for integer sparse recovery (Q2282769)

Compressed sensing is a relatively new mathematical paradigm that shows that a small number of linear measurements is enough to efficiently reconstruct a large dimensional signal under the assumption that the signal is sparse. The following extremal problem was raised by \textit{L. Fukshansky} et al. [Appl. Math. Comput. 340, 31--42 (2019; Zbl 1428.94036)]: Problem 1. Given integers \(k, m\), what is the maximum integer \(d=d(m,k)\) such that there exists \(m \times d\) matrix \(A\) with integer entries satisfying \(|a_{ij} | \le k\) such that all \(m \times m\) submatrices of \(A\) are non-degenerate? \textit{P. Brass} et al. [Research problems in discrete geometry. New York, NY: Springer (2005; Zbl 1086.52001), Chapter 10.2, Problem 6)] asked the following question: Problem 2. What is the minimum number \(M\) of \(s\)-dimensional linear subspaces necessary to cover \(m\)-dimensional \(k \times \cdots \times k\) grid \(K = \{x \in \mathbb Z^m: \|x\|_{\infty} \le k\}\) ? The authors of the present paper obtain new upper and lower bounds on \(d\) in Problem 1 and answer a to a special case of Problem 2.