More Like this

1. Super-resolution multi-reference alignment

   https://doi.org/10.1093/imaiai/iaab003  

   Bendory, Tamir; Jaffe, Ariel; Leeb, William; Sharon, Nir; Singer, Amit (February 2021, Information and Inference: A Journal of the IMA)

   null (Ed.)

   Abstract We study super-resolution multi-reference alignment, the problem of estimating a signal from many circularly shifted, down-sampled and noisy observations. We focus on the low SNR regime, and show that a signal in $${\mathbb{R}}^M$$ is uniquely determined when the number $$L$$ of samples per observation is of the order of the square root of the signal’s length ($$L=O(\sqrt{M})$$). Phrased more informally, one can square the resolution. This result holds if the number of observations is proportional to $$1/\textrm{SNR}^3$$. In contrast, with fewer observations recovery is impossible even when the observations are not down-sampled ($L=M$). The analysis combines tools from statistical signal processing and invariant theory. We design an expectation-maximization algorithm and demonstrate that it can super-resolve the signal in challenging SNR regimes. 

   more » « less
2. Decentralized Motion Inference and Registration of Neuropixel Data

   https://doi.org/10.1109/ICASSP39728.2021.9414145  

   Varol, Erdem; Boussard, Julien; Dethe, Nishchal; Winter, Olivier; Urai, Anne; Brain Laboratory, The International; Churchland, Anne; Steinmetz, Nick; Paninski, Liam (June 2021, ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   null (Ed.)

   Multi-electrode arrays such as "Neuropixels" probes enable the study of neuronal voltage signals at high temporal and single-cell spatial resolution. However, in vivo recordings from these devices often experience some shifting of the probe (due e.g. to animal movement), resulting in poorly localized voltage readings that in turn can corrupt estimates of neural activity. We introduce a new registration method to partially correct for this motion. In contrast to previous template-based registration methods, the proposed approach is decentralized, estimating shifts of the data recorded in multiple timebins with respect to one another, and then extracting a global registration estimate from the resulting estimated shift matrix. We find that the resulting decentralized registration is more robust and accurate than previous template-based approaches applied to both simulated and real data, but nonetheless some significant non-stationarity in the recovered neural activity remains that should be accounted for by downstream processing pipelines. Open source code is available at https://github.com/evarol/NeuropixelsRegistration. 

   more » « less
3. Phase retrieval of real-valued signals in a shift-invariant space

   https://doi.org/10.1016/j.acha.2018.11.002  

   Chen, Yang; Cheng, Cheng; Sun, Qiyu; Wang, Haichao (July 2020, Applied and computational harmonic analysis)

   In this paper, we consider an infinite-dimensional phase retrieval problem to reconstruct real-valued signals living in a shift-invariant space from their phaseless samples taken either on the whole line or on a discrete set with finite sampling density. We characterize all phase retrievable signals in a real-valued shift-invariant space using their nonseparability. For nonseparable signals generated by some function with support length L, we show that they can be well approximated, up to a sign, from their noisy phaseless samples taken on a discrete set with sampling density 2L-1 . In this paper, we also propose an algorithm with linear computational complexity to reconstruct nonseparable signals in a shift-invariant space from their phaseless samples corrupted by bounded noises. 

   more » « less
4. Anticipating regime shifts by mixing early warning signals from different nodes

   https://doi.org/10.1038/s41467-024-45476-9  

   Masuda, Naoki; Aihara, Kazuyuki; MacLaren, Neil G (December 2024, Nature Communications)

   Abstract Real systems showing regime shifts, such as ecosystems, are often composed of many dynamical elements interacting on a network. Various early warning signals have been proposed for anticipating regime shifts from observed data. However, it is unclear how one should combine early warning signals from different nodes for better performance. Based on theory of stochastic differential equations, we propose a method to optimize the node set from which to construct an early warning signal. The proposed method takes into account that uncertainty as well as the magnitude of the signal affects its predictive performance, that a large magnitude or small uncertainty of the signal in one situation does not imply the signal’s high performance, and that combining early warning signals from different nodes is often but not always beneficial. The method performs well particularly when different nodes are subjected to different amounts of dynamical noise and stress. 

   more » « less
5. Domain Sparsification of Discrete Distributions Using Entropic Independence

   Anari, Nima; Derezinski, Michal; Vuong, Thuy-Duong; Yang, Elizabeth (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   We present a framework for speeding up the time it takes to sample from discrete distributions $$\mu$$ defined over subsets of size $$k$$ of a ground set of $$n$$ elements, in the regime where $$k$$ is much smaller than $$n$$. We show that if one has access to estimates of marginals $$\mathbb{P}_{S\sim \mu}[i\in S]$$, then the task of sampling from $$\mu$$ can be reduced to sampling from related distributions $$\nu$$ supported on size $$k$$ subsets of a ground set of only $$n^{1-\alpha}\cdot \operatorname{poly}(k)$$ elements. Here, $$1/\alpha\in [1, k]$$ is the parameter of entropic independence for $$\mu$$. Further, our algorithm only requires sparsified distributions $$\nu$$ that are obtained by applying a sparse (mostly $$0$$) external field to $$\mu$$, an operation that for many distributions $$\mu$$ of interest, retains algorithmic tractability of sampling from $$\nu$$. This phenomenon, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals of $$\mu$$, and in return reduce the amortized cost needed to produce many samples from the distribution $$\mu$$, as is often needed in upstream tasks such as counting and inference. For a wide range of distributions where $$\alpha=\Omega(1)$$, our result reduces the domain size, and as a corollary, the cost-per-sample, by a $$\operatorname{poly}(n)$$ factor. Examples include monomers in a monomer-dimer system, non-symmetric determinantal point processes, and partition-constrained Strongly Rayleigh measures. Our work significantly extends the reach of prior work of Anari and Derezi\'nski who obtained domain sparsification for distributions with a log-concave generating polynomial (corresponding to $$\alpha=1$$). As a corollary of our new analysis techniques, we also obtain a less stringent requirement on the accuracy of marginal estimates even for the case of log-concave polynomials; roughly speaking, we show that constant-factor approximation is enough for domain sparsification, improving over $O(1/k)$ relative error established in prior work. 

   more » « less