An official website of the United States government
In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal's orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as ω(1/SNR^3). In this paper, using a generalization of the Chapman-Robbins bound for orbits and expansions of the χ2 divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as ω (1/SNR^2). This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation-maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model.
more »
« less
Super-resolution multi-reference alignment
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
- PAR ID:
- 10229885
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- ISSN:
- 2049-8772
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We analyze the channel capacity of a system with a large number of one-bit transceivers in a classical Rayleigh environment with perfect channel information at the receiver. With M transmitters and N =alpha*M receivers, we derive an expression of the capacity per transmitter C, where C <= min(1; aalpha), as a function of alpha and signal-to-noise ratio (SNR) rho, when M -> infinity. We show that our expression is a good approximation for small M, and provide simple approximations of C for various ranges of alpha and rho. We conclude that at high SNR, C reaches its upper limit of one only if alpha > 1:24. Expressions for determining when C “saturates” as a function of alpha and rho are given.more » « less
-
ABSTRACT We have re-observed $$\rm \sim$$40 low-inclination, star-forming galaxies from the MaNGA survey (σ ∼ 65 km s−1) at ∼6.5 times higher spectral resolution (σ ∼ 10 km s−1) using the HexPak integral field unit on the WIYN 3.5-m telescope. The aim of these observations is to calibrate MaNGA’s instrumental resolution and to characterize turbulence in the warm interstellar medium and ionized galactic outflows. Here we report the results for the Hα region observations as they pertain to the calibration of MaNGA’s spectral resolution. Remarkably, we find that the previously reported MaNGA line-spread-function (LSF) Gaussian width is systematically underestimated by only 1 per cent. The LSF increase modestly reduces the characteristic dispersion of H ii regions-dominated spectra sampled at 1–2 kpc spatial scales from 23 to 20 km s−1 in our sample, or a 25 per cent decrease in the random-motion kinetic energy. This commensurately lowers the dispersion zeropoint in the relation between line-width and star-formation rate surface-density in galaxies sampled on the same spatial scale. This modest zero-point shift does not appear to alter the power-law slope in the relation between line-width and star-formation rate surface-density. We also show that adopting a scheme whereby corrected line-widths are computed as the square root of the median of the difference in the squared measured line width and the squared LSF Gaussian avoids biases and allows for lower signal-to-noise data to be used reliably.more » « less
-
Point scanning imaging systems (e.g. scanning electron or laser scanning confocal microscopes) are perhaps the most widely used tools for high resolution cellular and tissue imaging. Like all other imaging modalities, the resolution, speed, sample preservation, and signal-to-noise ratio (SNR) of point scanning systems are difficult to optimize simultaneously. In particular, point scanning systems are uniquely constrained by an inverse relationship between imaging speed and pixel resolution. Here we show these limitations can be miti gated via the use of deep learning-based super-sampling of undersampled images acquired on a point-scanning system, which we termed point -scanning super-resolution (PSSR) imaging. Oversampled ground truth images acquired on scanning electron or Airyscan laser scanning confocal microscopes were used to generate semi-synthetictrain ing data for PSSR models that were then used to restore undersampled images. Remarkably, our EM PSSR model was able to restore undersampled images acquired with different optics, detectors, samples, or sample preparation methods in other labs . PSSR enabled previously unattainable xy resolution images with our serial block face scanning electron microscope system. For fluorescence, we show that undersampled confocal images combined with a multiframe PSSR model trained on Airyscan timelapses facilitates Airyscan-equivalent spati al resolution and SNR with ~100x lower laser dose and 16x higher frame rates than corresponding high-resolution acquisitions. In conclusion, PSSR facilitates point-scanning image acquisition with otherwise unattainable resolution, speed, and sensitivity.more » « less
-
Statistical and Computational Complexities of BFGS Quasi-Newton Method for Generalized Linear ModelsThe gradient descent (GD) method has been used widely to solve parameter estimation in generalized linear models (GLMs), a generalization of linear models when the link function can be non-linear. In GLMs with a polynomial link function, it has been shown that in the high signal-to-noise ratio (SNR) regime, due to the problem's strong convexity and smoothness, GD converges linearly and reaches the final desired accuracy in a logarithmic number of iterations. In contrast, in the low SNR setting, where the problem becomes locally convex, GD converges at a slower rate and requires a polynomial number of iterations to reach the desired accuracy. Even though Newton's method can be used to resolve the flat curvature of the loss functions in the low SNR case, its computational cost is prohibitive in high-dimensional settings as it is $$\mathcal{O}(d^3)$$, where $$d$$ the is the problem dimension. To address the shortcomings of GD and Newton's method, we propose the use of the BFGS quasi-Newton method to solve parameter estimation of the GLMs, which has a per iteration cost of $$\mathcal{O}(d^2)$$. When the SNR is low, for GLMs with a polynomial link function of degree $$p$$, we demonstrate that the iterates of BFGS converge linearly to the optimal solution of the population least-square loss function, and the contraction coefficient of the BFGS algorithm is comparable to that of Newton's method. Moreover, the contraction factor of the linear rate is independent of problem parameters and only depends on the degree of the link function $$p$$. Also, for the empirical loss with $$n$$ samples, we prove that in the low SNR setting of GLMs with a polynomial link function of degree $$p$$, the iterates of BFGS reach a final statistical radius of $$\mathcal{O}((d/n)^{\frac{1}{2p+2}})$$ after at most $$\log(n/d)$$ iterations. This complexity is significantly less than the number required for GD, which scales polynomially with $(n/d)$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imaiai/iaab003
