Given the compressed sensing measurements of an unknown vector $z \in \mathbb{R}^n$ using random matrices, we present a simple method to determine $z$ without solving any optimization problem or linear system. Our method uses $Θ(\log n)$ random sensing matrices in $\mathbb{R}^{k \times n}$ and runs in $O(kn\log n)$ time, where $k = Θ(s\log n)$ and $s$ is the number of nonzero coordinates in $z$. We adapt our method to determine the support set of $z$ and experimentally compare with some optimization-based methods on binary signals.

We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The $n$ input points are drawn from a hidden mixture of product distributions; we are only given an upper bound $m = o(\sqrt{n})$ on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of $Ω(1/n)$. For any $\varepsilon \in (0,1)$, after spending $O\bigl(mn\log^{O(1)} (mn) + m^{\varepsilon} n^{1+\varepsilon}\log(mn)\bigr)$ time in a training phase, our algorithm achieves an $O\bigl(\frac{1}{\varepsilon}n\log m + \frac{1}{\varepsilon}n2^{O(\log^* n)} + \frac{1}{\varepsilon}H\bigr)$ expected running time with probability at least $1 - O(1/n)$, where $H$ is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to $O\bigl(\frac{1}{\varepsilon}n\log m + \frac{1}{\varepsilon}H\bigr)$.

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.