Source author record

Man Ting Wong

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Computational Geometry Information Theory math.IT

Catalog footprint

Research overview

2works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Sparse Signal Recovery from Random Measurements

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.

preprint2020arXiv

A Generalization of Self-Improving Algorithms

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.