BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Dror Baron

Dror Baron appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine LearningDistributed, Parallel, and Cluster Computingeess.SPquant-phArtificial IntelligenceData Structures and Algorithmsmath.OCMethodologyQuantitative Methods

Catalog footprint

What is connected

30works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

30 published item(s)

preprint2026arXiv

Approximate Message Passing for Quantum State Tomography

Quantum state tomography (QST) is an indispensable tool for characterizing many-body quantum systems. However, due to the exponential scaling of the cost of the protocol with system size, many approaches have been developed for quantum states with specific structure, such as low-rank states. In this paper, we show how approximate message passing (AMP), an algorithmic framework for sparse signal recovery, can be used to perform low-rank QST. AMP provides asymptotically optimal performance guarantees for large sparse recovery problems, which suggests its utility for QST. We discuss the design challenges that come with applying AMP to QST, and show that by properly designing the AMP algorithm, we can reduce the reconstruction error by over an order of magnitude compared to existing approaches to low-rank QST. We also performed tomographic experiments on IBM Kingston and considered the effect of device noise on the reliability of the predicted fidelity of state preparation. Our work advances the state of low-rank QST and may be applicable to other quantum tomography protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Compressed Qubit Noise Spectroscopy: Piecewise-Linear Modeling and Rademacher Measurements

Random pulse sequences are a powerful method for qubit noise spectroscopy, enabling efficient reconstruction of sparse noise spectra. Here, we advance this method in two complementary directions. First, we extend the method using a regularizer based on the total generalized variation (TGV) norm, in order to reconstruct a larger class of noise spectra, namely piecewise-linear noise spectra, which more realistically model many physical systems. We show through numerical simulations that the new method resolves finer spectral features, while maintaining an order-of-magnitude speedup over conventional approaches to noise spectroscopy. Second, we simplify the experimental implementation of the method, by introducing Rademacher measurements for reconstructing sparse noise spectra. These measurements use pseudorandom pulse sequences that can be generated in real time from a short random seed, reducing experimental complexity without compromising reconstruction accuracy. Together, these developments broaden the reach of random pulse sequences for accurate and efficient noise characterization in realistic quantum systems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Contact Tracing Information Improves the Performance of Group Testing Algorithms

Group testing can help maintain a widespread testing program using fewer resources amid a pandemic. In group testing, we are given $n$ samples, one per individual. These samples are arranged into $m < n$ pooled samples, where each pool is obtained by mixing a subset of the $n$ individual samples. Infected individuals are then identified using a group testing algorithm. In this paper, we use side information (SI) collected from contact tracing (CT) within nonadaptive/single-stage group testing algorithms. We generate CT SI data by incorporating characteristics of disease spread between individuals. These data are fed into two signal and measurement models for group testing, and numerical results show that our algorithms provide improved sensitivity and specificity. We also show how to incorporate CT SI into the design of the pooling matrix. That said, our numerical results suggest that the utilization of SI in the pooling matrix design based on the minimization of a weighted coherence measure does not yield significant performance gains beyond the incorporation of SI in the group testing algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Neural Tangent Kernel Empowered Federated Learning

Federated learning (FL) is a privacy-preserving paradigm where multiple participants jointly solve a machine learning problem without sharing raw data. Unlike traditional distributed learning, a unique characteristic of FL is statistical heterogeneity, namely, data distributions across participants are different from each other. Meanwhile, recent advances in the interpretation of neural networks have seen a wide use of neural tangent kernels (NTKs) for convergence analyses. In this paper, we propose a novel FL paradigm empowered by the NTK framework. The paradigm addresses the challenge of statistical heterogeneity by transmitting update data that are more expressive than those of the conventional FL paradigms. Specifically, sample-wise Jacobian matrices, rather than model weights/gradients, are uploaded by participants. The server then constructs an empirical kernel matrix to update a global model without explicitly performing gradient descent. We further develop a variant with improved communication efficiency and enhanced privacy. Numerical results show that the proposed paradigm can achieve the same accuracy while reducing the number of communication rounds by an order of magnitude compared to federated averaging.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

mmWave Channel Estimation via Approximate Message Passing with Side Information

This work considers millimeter-wave channel estimation in a setting where parameters of the underlying mmWave channels are varying dynamically over time and there is a single drifting path. In this setting, channel estimates at time block $k$ can be used as side information (SI) when estimating the channel at block $k+1$. To estimate channel parameters, we employ an SI-aided (complex) approximate message passing algorithm and compare its performance to a benchmark based on orthogonal matching pursuit.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Noisy Pooled PCR for Virus Testing

Fast testing can help mitigate the coronavirus disease 2019 (COVID-19) pandemic. Despite their accuracy for single sample analysis, infectious diseases diagnostic tools, like RT-PCR, require substantial resources to test large populations. We develop a scalable approach for determining the viral status of pooled patient samples. Our approach converts group testing to a linear inverse problem, where false positives and negatives are interpreted as generated by a noisy communication channel, and a message passing algorithm estimates the illness status of patients. Numerical results reveal that our approach estimates patient illness using fewer pooled measurements than existing noisy group testing algorithms. Our approach can easily be extended to various applications, including where false negatives must be minimized. Finally, in a Utopian world we would have collaborated with RT-PCR experts; it is difficult to form such connections during a pandemic. We welcome new collaborators to reach out and help improve this work!

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rigorous State Evolution Analysis for Approximate Message Passing with Side Information

A common goal in many research areas is to reconstruct an unknown signal x from noisy linear measurements. Approximate message passing (AMP) is a class of low-complexity algorithms that can be used for efficiently solving such high-dimensional regression tasks. Often, it is the case that side information (SI) is available during reconstruction. For this reason, a novel algorithmic framework that incorporates SI into AMP, referred to as approximate message passing with side information (AMP-SI), has been recently introduced. In this work, we provide rigorous performance guarantees for AMP-SI when there are statistical dependencies between the signal and SI pairs and the entries of the measurement matrix are independent and identically distributed Gaussian. The AMP-SI performance is shown to be provably tracked by a scalar iteration referred to as state evolution. Moreover, we provide numerical examples that demonstrate empirically that the SE can predict the AMP-SI mean square error accurately.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximate Message Passing Algorithm with Universal Denoising and Gaussian Mixture Learning

We study compressed sensing (CS) signal reconstruction problems where an input signal is measured via matrix multiplication under additive white Gaussian noise. Our signals are assumed to be stationary and ergodic, but the input statistics are unknown; the goal is to provide reconstruction algorithms that are universal to the input statistics. We present a novel algorithmic framework that combines: (i) the approximate message passing (AMP) CS reconstruction framework, which solves the matrix channel recovery problem by iterative scalar channel denoising; (ii) a universal denoising scheme based on context quantization, which partitions the stationary ergodic signal denoising into independent and identically distributed (i.i.d.) subsequence denoising; and (iii) a density estimation approach that approximates the probability distribution of an i.i.d. sequence by fitting a Gaussian mixture (GM) model. In addition to the algorithmic framework, we provide three contributions: (i) numerical results showing that state evolution holds for non-separable Bayesian sliding-window denoisers; (ii) an i.i.d. denoiser based on a modified GM learning algorithm; and (iii) a universal denoiser that does not need information about the range where the input takes values from or require the input signal to be bounded. We provide two implementations of our universal CS recovery algorithm with one being faster and the other being more accurate. The two implementations compare favorably with existing universal reconstruction algorithms in terms of both reconstruction quality and runtime.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multi-Processor Approximate Message Passing Using Lossy Compression

In this paper, a communication-efficient multi-processor compressed sensing framework based on the approximate message passing algorithm is proposed. We perform lossy compression on the data being communicated between processors, resulting in a reduction in communication costs with a minor degradation in recovery quality. In the proposed framework, a new state evolution formulation takes the quantization error into account, and analytically determines the coding rate required in each iteration. Two approaches for allocating the coding rate, an online back-tracking heuristic and an optimal allocation scheme based on dynamic programming, provide significant reductions in communication costs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Trade-offs in Multi-Processor Approximate Message Passing

We consider large-scale linear inverse problems in Bayesian settings. We follow a recent line of work that applies the approximate message passing (AMP) framework to multi-processor (MP) computational systems, where each processor node stores and processes a subset of rows of the measurement matrix along with corresponding measurements. In each MP-AMP iteration, nodes of the MP system and its fusion center exchange lossily compressed messages pertaining to their estimates of the input. In this setup, we derive the optimal per-iteration coding rates using dynamic programming. We analyze the excess mean squared error (EMSE) beyond the minimum mean squared error (MMSE), and prove that, in the limit of low EMSE, the optimal coding rates increase approximately linearly per iteration. Additionally, we obtain that the combined cost of computation and communication scales with the desired estimation quality according to $O(\log^2(1/\text{EMSE}))$. Finally, we study trade-offs between the physical costs of the estimation process including computation time, communication loads, and the estimation quality as a multi-objective optimization problem, and characterize the properties of the Pareto optimal surfaces.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Performance Trade-Offs in Multi-Processor Approximate Message Passing

We consider large-scale linear inverse problems in Bayesian settings. Our general approach follows a recent line of work that applies the approximate message passing (AMP) framework in multi-processor (MP) computational systems by storing and processing a subset of rows of the measurement matrix along with corresponding measurements at each MP node. In each MP-AMP iteration, nodes of the MP system and its fusion center exchange lossily compressed messages pertaining to their estimates of the input. There is a trade-off between the physical costs of the reconstruction process including computation time, communication loads, and the reconstruction quality, and it is impossible to simultaneously minimize all the costs. We pose this minimization as a multi-objective optimization problem (MOP), and study the properties of the best trade-offs (Pareto optimality) in this MOP. We prove that the achievable region of this MOP is convex, and conjecture how the combined cost of computation and communication scales with the desired mean squared error. These properties are verified numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximate Message Passing in Coded Aperture Snapshot Spectral Imaging

We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The approximate message passing (AMP) framework is utilized to reconstruct hyperspectral images from CASSI measurements, and an adaptive Wiener filter is employed as a three-dimensional image denoiser within AMP. We call our algorithm "AMP-3D-Wiener." The simulation results show that AMP-3D-Wiener outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given the same amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-3D-Wiener need not tune any parameters, which simplifies the reconstruction process.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Compressive Hyperspectral Imaging via Approximate Message Passing

We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The CASSI imaging process can be modeled as suppressing three-dimensional coded and shifted voxels and projecting these onto a two-dimensional plane, such that the number of acquired measurements is greatly reduced. On the other hand, because the measurements are highly compressive, the reconstruction process becomes challenging. We previously proposed a compressive imaging reconstruction algorithm that is applied to two-dimensional images based on the approximate message passing (AMP) framework. AMP is an iterative algorithm that can be used in signal and image reconstruction by performing denoising at each iteration. We employed an adaptive Wiener filter as the image denoiser, and called our algorithm "AMP-Wiener." In this paper, we extend AMP-Wiener to three-dimensional hyperspectral image reconstruction, and call it "AMP-3D-Wiener." Applying the AMP framework to the CASSI system is challenging, because the matrix that models the CASSI system is highly sparse, and such a matrix is not suitable to AMP and makes it difficult for AMP to converge. Therefore, we modify the adaptive Wiener filter and employ a technique called damping to solve for the divergence issue of AMP. Our approach is applied in nature, and the numerical experiments show that AMP-3D-Wiener outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given a similar amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-3D-Wiener need not tune any parameters, which simplifies the reconstruction process.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Compressive Imaging via Approximate Message Passing with Image Denoising

We consider compressive imaging problems, where images are reconstructed from a reduced number of linear measurements. Our objective is to improve over existing compressive imaging algorithms in terms of both reconstruction error and runtime. To pursue our objective, we propose compressive imaging algorithms that employ the approximate message passing (AMP) framework. AMP is an iterative signal reconstruction algorithm that performs scalar denoising at each iteration; in order for AMP to reconstruct the original input signal well, a good denoiser must be used. We apply two wavelet based image denoisers within AMP. The first denoiser is the "amplitude-scaleinvariant Bayes estimator" (ABE), and the second is an adaptive Wiener filter; we call our AMP based algorithms for compressive imaging AMP-ABE and AMP-Wiener. Numerical results show that both AMP-ABE and AMP-Wiener significantly improve over the state of the art in terms of runtime. In terms of reconstruction quality, AMP-Wiener offers lower mean square error (MSE) than existing compressive imaging algorithms. In contrast, AMP-ABE has higher MSE, because ABE does not denoise as well as the adaptive Wiener filter.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Mismatched Estimation in Large Linear Systems

We study the excess mean square error (EMSE) above the minimum mean square error (MMSE) in large linear systems where the posterior mean estimator (PME) is evaluated with a postulated prior that differs from the true prior of the input signal. We focus on large linear systems where the measurements are acquired via an independent and identically distributed random matrix, and are corrupted by additive white Gaussian noise (AWGN). The relationship between the EMSE in large linear systems and EMSE in scalar channels is derived, and closed form approximations are provided. Our analysis is based on the decoupling principle, which links scalar channels to large linear system analyses. Numerical examples demonstrate that our closed form approximations are accurate.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Parallel Two-Pass MDL Context Tree Algorithm for Universal Source Coding

We present a novel lossless universal source coding algorithm that uses parallel computational units to increase the throughput. The length-$N$ input sequence is partitioned into $B$ blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of $B$, but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) source underlying the entire input, and then encode each of the $B$ blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i.e., its computational complexity is $O(N/B)$. Its redundancy is approximately $B\log(N/B)$ bits above Rissanen's lower bound on universal coding performance, with respect to any tree source whose maximal depth is at most $\log(N/B)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Compressed Sensing via Universal Denoising and Approximate Message Passing

We study compressed sensing (CS) signal reconstruction problems where an input signal is measured via matrix multiplication under additive white Gaussian noise. Our signals are assumed to be stationary and ergodic, but the input statistics are unknown; the goal is to provide reconstruction algorithms that are universal to the input statistics. We present a novel algorithm that combines: (i) the approximate message passing (AMP) CS reconstruction framework, which converts the matrix channel recovery problem into scalar channel denoising; (ii) a universal denoising scheme based on context quantization, which partitions the stationary ergodic signal denoising into independent and identically distributed (i.i.d.) subsequence denoising; and (iii) a density estimation approach that approximates the probability distribution of an i.i.d. sequence by fitting a Gaussian mixture (GM) model. In addition to the algorithmic framework, we provide three contributions: (i) numerical results showing that state evolution holds for non-separable Bayesian sliding-window denoisers; (ii) a universal denoiser that does not require the input signal to be bounded; and (iii) we modify the GM learning algorithm, and extend it to an i.i.d. denoiser. Our universal CS recovery algorithm compares favorably with existing reconstruction algorithms in terms of both reconstruction quality and runtime, despite not knowing the input statistics of the stationary ergodic signal.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Empirical Bayes and Full Bayes for Signal Estimation

We consider signals that follow a parametric distribution where the parameter values are unknown. To estimate such signals from noisy measurements in scalar channels, we study the empirical performance of an empirical Bayes (EB) approach and a full Bayes (FB) approach. We then apply EB and FB to solve compressed sensing (CS) signal estimation problems by successively denoising a scalar Gaussian channel within an approximate message passing (AMP) framework. Our numerical results show that FB achieves better performance than EB in scalar channel denoising problems when the signal dimension is small. In the CS setting, the signal dimension must be large enough for AMP to work well; for large signal dimensions, AMP has similar performance with FB and EB.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Recovery from Linear Measurements with Complexity-Matching Universal Signal Estimation

We study the compressed sensing (CS) signal estimation problem where an input signal is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the input signal during recovery, the signal structure that can be leveraged is often not known a priori. In this paper, we consider universal CS recovery, where the statistics of a stationary ergodic signal source are estimated simultaneously with the signal itself. Inspired by Kolmogorov complexity and minimum description length, we focus on a maximum a posteriori (MAP) estimation framework that leverages universal priors to match the complexity of the source. Our framework can also be applied to general linear inverse problems where more measurements than in CS might be needed. We provide theoretical results that support the algorithmic feasibility of universal MAP estimation using a Markov chain Monte Carlo implementation, which is computationally challenging. We incorporate some techniques to accelerate the algorithm while providing comparable and in many cases better reconstruction quality than existing algorithms. Experimental results show the promise of universality in CS, particularly for low-complexity sources that do not exhibit standard sparsity or compressibility.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Two-Part Reconstruction with Noisy-Sudocodes

We develop a two-part reconstruction framework for signal recovery in compressed sensing (CS), where a fast algorithm is applied to provide partial recovery in Part 1, and a CS algorithm is applied to complete the residual problem in Part 2. Partitioning the reconstruction process into two complementary parts provides a natural trade-off between runtime and reconstruction quality. To exploit the advantages of the two-part framework, we propose a Noisy-Sudocodes algorithm that performs two-part reconstruction of sparse signals in the presence of measurement noise. Specifically, we design a fast algorithm for Part 1 of Noisy-Sudocodes that identifies the zero coefficients of the input signal from its noisy measurements. Many existing CS algorithms could be applied to Part 2, and we investigate approximate message passing (AMP) and binary iterative hard thresholding (BIHT). For Noisy-Sudocodes with AMP in Part 2, we provide a theoretical analysis that characterizes the trade-off between runtime and reconstruction quality. In a 1-bit CS setting where a new 1-bit quantizer is constructed for Part 1 and BIHT is applied to Part 2, numerical results show that the Noisy-Sudocodes algorithm improves over BIHT in both runtime and reconstruction quality.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Wiener Filters in Gaussian Mixture Signal Estimation with Infinity-Norm Error

Consider the estimation of a signal ${\bf x}\in\mathbb{R}^N$ from noisy observations ${\bf r=x+z}$, where the input~${\bf x}$ is generated by an independent and identically distributed (i.i.d.) Gaussian mixture source, and ${\bf z}$ is additive white Gaussian noise (AWGN) in parallel Gaussian channels. Typically, the $\ell_2$-norm error (squared error) is used to quantify the performance of the estimation process. In contrast, we consider the $\ell_\infty$-norm error (worst case error). For this error metric, we prove that, in an asymptotic setting where the signal dimension $N\to\infty$, the $\ell_\infty$-norm error always comes from the Gaussian component that has the largest variance, and the Wiener filter asymptotically achieves the optimal expected $\ell_\infty$-norm error. The i.i.d. Gaussian mixture case is easily applicable to i.i.d. Bernoulli-Gaussian distributions, which are often used to model sparse signals. Finally, our results can be extended to linear mixing systems with i.i.d. Gaussian mixture inputs, in settings where a linear mixing system can be decoupled to parallel Gaussian channels.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Measurement Bounds for Sparse Signal Ensembles via Graphical Models

In compressive sensing, a small collection of linear projections of a sparse signal contains enough information to permit signal recovery. Distributed compressive sensing (DCS) extends this framework by defining ensemble sparsity models, allowing a correlated ensemble of sparse signals to be jointly recovered from a collection of separately acquired compressive measurements. In this paper, we introduce a framework for modeling sparse signal ensembles that quantifies the intra- and inter-signal dependencies within and among the signals. This framework is based on a novel bipartite graph representation that links the sparse signal coefficients with the measurements obtained for each signal. Using our framework, we provide fundamental bounds on the number of noiseless measurements that each sensor must collect to ensure that the signals are jointly recoverable.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Mixture Gaussian Signal Estimation with L_infty Error Metric

We consider the problem of estimating an input signal from noisy measurements in both parallel scalar Gaussian channels and linear mixing systems. The performance of the estimation process is quantified by the $\ell_\infty$ norm error metric. We first study the minimum mean $\ell_\infty$ error estimator in parallel scalar Gaussian channels, and verify that, when the input is independent and identically distributed (i.i.d.) mixture Gaussian, the Wiener filter is asymptotically optimal with probability 1. For linear mixing systems with i.i.d. sparse Gaussian or mixture Gaussian inputs, under the assumption that the relaxed belief propagation (BP) algorithm matches Tanaka's fixed point equation, applying the Wiener filter to the output of relaxed BP is also asymptotically optimal with probability 1. However, in order to solve the practical problem where the signal dimension is finite, we apply an estimation algorithm that has been proposed in our previous work, and illustrate that an $\ell_\infty$ error minimizer can be approximated by an $\ell_p$ error minimizer provided the value of $p$ is properly chosen.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Performance Regions in Compressed Sensing from Noisy Measurements

In this paper, compressed sensing with noisy measurements is addressed. The theoretically optimal reconstruction error is studied by evaluating Tanaka's equation. The main contribution is to show that in several regions, which have different measurement rates and noise levels, the reconstruction error behaves differently. This paper also evaluates the performance of the belief propagation (BP) signal reconstruction method in the regions discovered. When the measurement rate and the noise level lie in a certain region, BP is suboptimal with respect to Tanaka's equation, and it may be possible to develop reconstruction algorithms with lower error in that region.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Signal Estimation with Additive Error Metrics in Compressed Sensing

Compressed sensing typically deals with the estimation of a system input from its noise-corrupted linear measurements, where the number of measurements is smaller than the number of input components. The performance of the estimation process is usually quantified by some standard error metric such as squared error or support set error. In this correspondence, we consider a noisy compressed sensing problem with any arbitrary error metric. We propose a simple, fast, and highly general algorithm that estimates the original signal by minimizing the error metric defined by the user. We verify that our algorithm is optimal owing to the decoupling principle, and we describe a general method to compute the fundamental information-theoretic performance limit for any error metric. We provide two example metrics --- minimum mean absolute error and minimum mean support error --- and give the theoretical performance limits for these two cases. Experimental results show that our algorithm outperforms methods such as relaxed belief propagation (relaxed BP) and compressive sampling matching pursuit (CoSaMP), and reaches the suggested theoretical limits for our two example metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Signal reconstruction in linear mixing systems with different error metrics

We consider the problem of reconstructing a signal from noisy measurements in linear mixing systems. The reconstruction performance is usually quantified by standard error metrics such as squared error, whereas we consider any additive error metric. Under the assumption that relaxed belief propagation (BP) can compute the posterior in the large system limit, we propose a simple, fast, and highly general algorithm that reconstructs the signal by minimizing the user-defined error metric. For two example metrics, we provide performance analysis and convincing numerical results. Finally, our algorithm can be adjusted to minimize the $\ell_\infty$ error, which is not additive. Interestingly, $\ell_{\infty}$ minimization only requires to apply a Wiener filter to the output of relaxed BP.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Two-Part Reconstruction in Compressed Sensing

Two-part reconstruction is a framework for signal recovery in compressed sensing (CS), in which the advantages of two different algorithms are combined. Our framework allows to accelerate the reconstruction procedure without compromising the reconstruction quality. To illustrate the efficacy of our two-part approach, we extend the author's previous Sudocodes algorithm and make it robust to measurement noise. In a 1-bit CS setting, promising numerical results indicate that our algorithm offers both a reduction in run-time and improvement in reconstruction quality.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An MCMC Approach to Universal Lossy Compression of Analog Sources

Motivated by the Markov chain Monte Carlo (MCMC) approach to the compression of discrete sources developed by Jalali and Weissman, we propose a lossy compression algorithm for analog sources that relies on a finite reproduction alphabet, which grows with the input length. The algorithm achieves, in an appropriate asymptotic sense, the optimum Shannon theoretic tradeoff between rate and distortion, universally for stationary ergodic continuous amplitude sources. We further propose an MCMC-based algorithm that resorts to a reduced reproduction alphabet when such reduction does not prevent achieving the Shannon limit. The latter algorithm is advantageous due to its reduced complexity and improved rates of convergence when employed on sources with a finite and small optimum reproduction alphabet.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Fault Identification via Non-parametric Belief Propagation

We consider the problem of identifying a pattern of faults from a set of noisy linear measurements. Unfortunately, maximum a posteriori probability estimation of the fault pattern is computationally intractable. To solve the fault identification problem, we propose a non-parametric belief propagation approach. We show empirically that our belief propagation solver is more accurate than recent state-of-the-art algorithms including interior point methods and semidefinite programming. Our superior performance is explained by the fact that we take into account both the binary nature of the individual faults and the sparsity of the fault pattern arising from their rarity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Information Complexity and Estimation

We consider an input $x$ generated by an unknown stationary ergodic source $X$ that enters a signal processing system $J$, resulting in $w=J(x)$. We observe $w$ through a noisy channel, $y=z(w)$; our goal is to estimate x from $y$, $J$, and knowledge of $f_{Y|W}$. This is universal estimation, because $f_X$ is unknown. We provide a formulation that describes a trade-off between information complexity and noise. Initial theoretical, algorithmic, and experimental evidence is presented in support of our approach.

0 citations0 reviewsNo code linkedOpen access