SOLVING ILL-CONDITIONED POLYNOMIAL EQUATIONS USING SCORE-BASED PRIORS WITH APPLICATION TO MULTI-TARGET DETECTION

Rafi Beinhorn, Shay Kreymer, Amnon Balanov, Michael Cohen, Alon Zabatani, Tamir Bendory · 2025

Read SOLVING ILL-CONDITIONED POLYNOMIAL EQUATIONS USING SCORE-BASED PRIORS WITH APPLICATION TO MULTI-TARGET DETECTION by Rafi Beinhorn, Shay Kreymer, Amnon Balanov, Michael Cohen, Alon Zabatani, Tamir Bendory (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11397.txt.

Introduction

Rafi Beinhorn and 5 co-authors stabilize a hard class of inverse problems with generative priors in this 2025 paper. Many recovery tasks boil down to solving polynomial equations built from low-order moments of a signal, and those systems are notoriously ill-conditioned: tiny noise swings the answer wildly.

Their framework pairs moment-based estimators with score-based diffusion priors, using the learned prior as a regularizer. That gives generative models a new job, steadying polynomial recovery rather than producing samples. The test case is multi-target detection in heavy noise. Diffusion priors clearly improved recovery from third-order moments and made a super-resolution version of the problem, otherwise unsolvable, feasible. Experiments on handwritten digit data confirmed the gains across noise levels.

Catalog record

CREATORRafi Beinhorn, Shay Kreymer, Amnon Balanov, Michael Cohen, Alon Zabatani, Tamir Bendory
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11397

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SOLVING ILL-CONDITIONED POLYNOMIAL EQUATIONS USING SCORE-BASED PRIORS WITH APPLICATION TO MULTI-TARGET DETECTION Rafi Beinhorn, Shay Kreymer, Amnon Balanov, Michael Cohen, Alon Zabatani, Tamir Bendory Abstract Recovering signals from low-order moments is a fundamental yet notoriously difficult task in inverse problems. This recovery process often reduces to solving ill-conditioned systems of polynomial equations. In this work, we propose a new framework that integrates score-based diffusion priors with moment-based estimators to regularize and solve these nonlinear inverse problems. This introduces a new role for generative models: stabilizing polynomial recovery from noisy statistical features. As a concrete application, we study the multi-target detection (MTD) model in the high-noise regime. We demonstrate two main results: (i) diffusion priors substantially improve recovery from third-order moments, and (ii) they make the super-resolution MTD problem, otherwise ill-posed, feasible. Numerical experiments on MNIST data confirm consistent gains in reconstruction accuracy across SNR levels. Our results suggest a promising new direction for combining generative priors with nonlinear polynomial inverse problems. † † address: School of Electrical and Computer Engineering, Tel Aviv University, Tel Aviv, Israel 1 Introduction The reconstruction of signals from limited and noisy measurements is a fundamental challenge in imaging, communications, and machine learning. A particularly difficult case arises when one aims to infer signals from low-order moments , leading to polynomial systems that are typically ill-conditioned or even underdetermined [ 1 , 2 ] . In some settings, such as super-resolution, the problem is fundamentally ill-posed without strong prior knowledge [ 3 , 4 ] . Recovery from low-order moments can be formulated as solving a system of polynomial equations. The hardness of polynomial recovery is well known: solving general polynomial systems is NP-hard [ 2 ] . Classical approaches, including tensor decompositions for latent variable models [ 5 ] and convex relaxations based on sum-of-squares, semidefinite programming, or the Lasserre hierarchy [ 1 , 2 ] , offer theoretical guarantees under restrictive assumptions but are computationally intensive and often unstable at low SNR. Recent work therefore seeks more scalable alternatives [ 6 , 7 ] . Figure 1: Mean estimation error as a function of SNR for recovering a target image from an MTD measurement using moments up to the third-order, with and without score-based diffusion model prior. Evidently, incorporating the score-based prior consistently improves performance across all SNR levels. To illustrate the visual impact, recovered images for a representative digit are shown at selected SNR values, demonstrating the improvement in reconstruction quality. In the last dozen years, data-driven priors have revolutionized linear inverse problems: plug-and-play methods [ 8 ] , GAN priors [ 9 ] , and diffusion models [ 10 , 11 ] have achieved state-of-the-art results in denoising, deblurring, and super-resolution. Yet these advances almost exclusively target linear forward models. In this work, we turn our attention to nonlinear polynomial inverse problems arising from moment inversion, which are considerably more unstable and remain largely unexplored in the generative modeling literature, and, to the best of our knowledge, have not yet been addressed. Our results show that such priors can effectively regularize and stabilize these systems, thereby extending the reach of generative models beyond linear operators. 1.1 The multi-target detection model One particularly challenging task involving the inference of signals from low-order moments is the application of the method of moments to the task of multi-target detection (MTD) [ 12 ] . MTD entails estimating an image, x\in\mathbb{R}^{L\times L} , from a noisy measurement, y\in\mathbb{R}^{N\times N} , which contains multiple randomly translated copies of the image. This measurement process is described by: y[\vec{\ell}]=\sum_{m=1}^{M}x[\vec{\ell}-\vec{\ell}_{m}]+\varepsilon[\vec{\ell}], (1) where \vec{\ell}_{m}\in\{L+1,\ldots,N-L\}^{2} denote unknown arbitrary translations, M is the number of occurrences of x , and \varepsilon[\vec{\ell}] represents i.i.d. Gaussian noise with zero mean and variance \sigma^{2} . The goal is to estimate the target signal x , while the translations are treated as nuisance variables, and their estimation is not required. MTD serves as an abstraction for cryo-EM [ 13 , 14 , 15 ] , central to efforts in reconstructing 3-D molecular structures from raw data [ 16 , 17 ] . In this work, we focus on the high noise regime and follow [ 12 , 18 , 16 , 19 ] in approaching MTD through autocorrelation analysis, a special case of the method of moments. While autocorrelation analysis has shown some success for MTD, it remains numerically inferior to alternative approaches. In particular, when information is incomplete, as in the super-resolution setting considered later in this paper, the method breaks down entirely. This limitation is especially critical in three dimensions: prior attempts [ 16 ] demonstrated the potential of autocorrelation analysis for 3-D MTD, but also revealed severe numerical challenges. In three dimensions, higher-order moment estimators are markedly more sensitive to noise, and the rapid growth in the number of equations further exacerbates ill-conditioning, making stable recovery increasingly infeasible. These difficulties highlight a critical gap: moment-based methods alone are inadequate in high-dimensional, low-SNR regimes. Bridging this gap requires reconstruction strategies that integrate stronger, data-driven priors to regularize inversion and improve robustness. In this work, we pursue this direction by introducing score-based diffusion models as powerful generative priors for 3-D reconstruction. 1.2 Score-based diffusion models To overcome the instability of classical moment-based methods, we introduce score-based diffusion models as effective, data-driven priors. Diffusion models [ 20 ] are probabilistic generative frameworks that progressively corrupt data with Gaussian noise and learn to reverse this process, thereby capturing the underlying distribution of natural signals. Score-based stochastic differential equations (score-SDE) [ 21 ] is a popular diffusion model that makes use of the Stein score, i.e., the gradient of the log probability density. The key idea behind score-SDE is to perturb the data with a sequence of intensifying Gaussian noise governed by a closed-form stochastic differential equation, and jointly estimate the score functions for all noisy data distributions by training a deep neural network, conditioned on the noise levels. The integration of such priors aims to regularize and solve intrinsically ill-conditioned polynomial systems. 1.3 Main contribution Building upon these ideas, we propose a framework that integrates score-based diffusion priors into the method of moments paradigm to tackle ill-conditioned polynomial systems. We evaluate this approach in the context of MTD through two representative scenarios. First, we study the recovery of the target signal x via autocorrelation analysis, which gives rise to an ill-conditioned polynomial system. In earlier work [ 22 ] , we demonstrated the potential of score-based priors within the expectation-maximization framework for this setting. Second, we address the super-resolution MTD problem, which is intrinsically ill-posed, as it entails not only recovering the target image but also reconstructing fine-scale features beyond the native resolution of the measurements. In both cases, the score-based diffusion prior serves to inject data-driven structural knowledge into the recovery process, thereby regularizing the underlying nonlinear polynomial systems and mitigating their sensitivity to noise and underdetermination. More generally, our contribution is a method for solving ill-conditioned systems of nonlinear polynomial equations by combining the statistical consistency of moment-based estimators with the expressive power of modern generative models. We demonstrate this framework on two challenging instances of the MTD problem, showing that it enables robust reconstruction in regimes where traditional techniques struggle. The remainder of the paper

Read the complete text