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

Philip Schniter

Philip Schniter 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 LearningComputer Visioneess.IVNetworking and Internet Architecturecond-mat.dis-nneess.SPmath.OCNeural and Evolutionary ComputingSystems and Control

Catalog footprint

What is connected

40works
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

40 published item(s)

preprint2022arXiv

Denoising Generalized Expectation-Consistent Approximation for MR Image Recovery

To solve inverse problems, plug-and-play (PnP) methods replace the proximal step in a convex optimization algorithm with a call to an application-specific denoiser, often implemented using a deep neural network (DNN). Although such methods yield accurate solutions, they can be improved. For example, denoisers are usually designed/trained to remove white Gaussian noise, but the denoiser input error in PnP algorithms is usually far from white or Gaussian. Approximate message passing (AMP) methods provide white and Gaussian denoiser input error, but only when the forward operator is sufficiently random. In this work, for Fourier-based forward operators, we propose a PnP algorithm based on generalized expectation-consistent (GEC) approximation -- a close cousin of AMP -- that offers predictable error statistics at each iteration, as well as a new DNN denoiser that leverages those statistics. We apply our approach to magnetic resonance (MR) image recovery and demonstrate its advantages over existing PnP and AMP methods.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Expectation Consistent Plug-and-Play for MRI

For image recovery problems, plug-and-play (PnP) methods have been developed that replace the proximal step in an optimization algorithm with a call to an application-specific denoiser, often implemented using a deep neural network. Although such methods have been successful, they can be improved. For example, the denoiser is often trained using white Gaussian noise, while PnP's denoiser input error is often far from white and Gaussian, with statistics that are difficult to predict from iteration to iteration. PnP methods based on approximate message passing (AMP) are an exception, but only when the forward operator behaves like a large random matrix. In this work, we design a PnP method using the expectation consistent (EC) approximation algorithm, a generalization of AMP, that offers predictable error statistics at each iteration, from which a deep-net denoiser can be effectively trained.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Free-breathing Cardiovascular MRI Using a Plug-and-Play Method with Learned Denoiser

Cardiac magnetic resonance imaging (CMR) is a noninvasive imaging modality that provides a comprehensive evaluation of the cardiovascular system. The clinical utility of CMR is hampered by long acquisition times, however. In this work, we propose and validate a plug-and-play (PnP) method for CMR reconstruction from undersampled multi-coil data. To fully exploit the rich image structure inherent in CMR, we pair the PnP framework with a deep learning (DL)-based denoiser that is trained using spatiotemporal patches from high-quality, breath-held cardiac cine images. The resulting "PnP-DL" method iterates over data consistency and denoising subroutines. We compare the reconstruction performance of PnP-DL to that of compressed sensing (CS) using eight breath-held and ten real-time (RT) free-breathing cardiac cine datasets. We find that, for breath-held datasets, PnP-DL offers more than one dB advantage over commonly used CS methods. For RT free-breathing datasets, where ground truth is not available, PnP-DL receives higher scores in qualitative evaluation. The results highlight the potential of PnP-DL to accelerate RT CMR.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Inference in Multi-Layer Networks with Matrix-Valued Unknowns

We consider the problem of inferring the input and hidden variables of a stochastic multi-layer neural network from an observation of the output. The hidden variables in each layer are represented as matrices. This problem applies to signal recovery via deep generative prior models, multi-task and mixed regression and learning certain classes of two-layer neural networks. A unified approximation algorithm for both MAP and MMSE inference is proposed by extending a recently-developed Multi-Layer Vector Approximate Message Passing (ML-VAMP) algorithm to handle matrix-valued unknowns. It is shown that the performance of the proposed Multi-Layer Matrix VAMP (ML-Mat-VAMP) algorithm can be exactly predicted in a certain random large-system limit, where the dimensions $N\times d$ of the unknown quantities grow as $N\rightarrow\infty$ with $d$ fixed. In the two-layer neural-network learning problem, this scaling corresponds to the case where the number of input features and training samples grow to infinity but the number of hidden nodes stays fixed. The analysis enables a precise prediction of the parameter and test error of the learning.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multi-User Detection Based on Expectation Propagation for the Non-Coherent SIMO Multiple Access Channel

We consider the non-coherent single-input multiple-output (SIMO) multiple access channel with general signaling under spatially correlated Rayleigh block fading. We propose a novel soft-output multi-user detector that computes an approximate marginal posterior of each transmitted signal using only the knowledge about the channel distribution. Our detector is based on expectation propagation (EP) approximate inference and has polynomial complexity in the number of users, the number of receive antennas, and channel coherence time. We also propose two simplifications of this detector with reduced complexity. With Grassmannian signaling, the proposed detectors outperform a state-of-the-art non-coherent detector with projection-based interference mitigation. With pilot-assisted signaling, the EP detector outperforms, in terms of symbol error rate, some conventional coherent pilot-based detectors, including a sphere decoder and a joint channel estimation-data detection scheme. Our EP-based detectors produce accurate approximates of the true posterior leading to high achievable sum-rates. The gains of these detectors are further observed in terms of the bit error rate when using their soft outputs for a turbo channel decoder.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

OCMR (v1.0)--Open-Access Multi-Coil k-Space Dataset for Cardiovascular Magnetic Resonance Imaging

Cardiovascular MRI (CMR) is a non-invasive imaging modality that provides excellent soft-tissue contrast without the use of ionizing radiation. Physiological motions and limited speed of MRI data acquisition necessitate development of accelerated methods, which typically rely on undersampling. Recovering diagnostic quality CMR images from highly undersampled data has been an active area of research. Recently, several data acquisition and processing methods have been proposed to accelerate CMR. The availability of data to objectively evaluate and compare different reconstruction methods could expedite innovation and promote clinical translation of these methods. In this work, we introduce an open-access dataset, called OCMR, that provides multi-coil k-space data from 53 fully sampled and 212 prospectively undersampled cardiac cine series.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Plug and play methods for magnetic resonance imaging (long version)

Magnetic Resonance Imaging (MRI) is a non-invasive diagnostic tool that provides excellent soft-tissue contrast without the use of ionizing radiation. Compared to other clinical imaging modalities (e.g., CT or ultrasound), however, the data acquisition process for MRI is inherently slow, which motivates undersampling and thus drives the need for accurate, efficient reconstruction methods from undersampled datasets. In this article, we describe the use of "plug-and-play" (PnP) algorithms for MRI image recovery. We first describe the linearly approximated inverse problem encountered in MRI. Then we review several PnP methods, where the unifying commonality is to iteratively call a denoising subroutine as one step of a larger optimization-inspired algorithm. Next, we describe how the result of the PnP method can be interpreted as a solution to an equilibrium equation, allowing convergence analysis from the equilibrium perspective. Finally, we present illustrative examples of PnP methods applied to MRI image recovery.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis

Estimating a vector $\mathbf{x}$ from noisy linear measurements $\mathbf{Ax}+\mathbf{w}$ often requires use of prior knowledge or structural constraints on $\mathbf{x}$ for accurate reconstruction. Several recent works have considered combining linear least-squares estimation with a generic or "plug-in" denoiser function that can be designed in a modular manner based on the prior knowledge about $\mathbf{x}$. While these methods have shown excellent performance, it has been difficult to obtain rigorous performance guarantees. This work considers plug-in denoising combined with the recently-developed Vector Approximate Message Passing (VAMP) algorithm, which is itself derived via Expectation Propagation techniques. It shown that the mean squared error of this "plug-and-play" VAMP can be exactly predicted for high-dimensional right-rotationally invariant random $\mathbf{A}$ and Lipschitz denoisers. The method is demonstrated on applications in image recovery and parametric bilinear estimation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Denoising based Vector Approximate Message Passing

The denoising-based approximate message passing (D-AMP) methodology, recently proposed by Metzler, Maleki, and Baraniuk, allows one to plug in sophisticated denoisers like BM3D into the AMP algorithm to achieve state-of-the-art compressive image recovery. But AMP diverges with small deviations from the i.i.d.-Gaussian assumption on the measurement matrix. Recently, the vector AMP (VAMP) algorithm has been proposed to fix this problem. In this work, we show that the benefits of VAMP extend to D-VAMP.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed-points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed-points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization

Generalized Linear Models (GLMs), where a random vector $\mathbf{x}$ is observed through a noisy, possibly nonlinear, function of a linear transform $\mathbf{z}=\mathbf{Ax}$ arise in a range of applications in nonlinear filtering and regression. Approximate Message Passing (AMP) methods, based on loopy belief propagation, are a promising class of approaches for approximate inference in these models. AMP methods are computationally simple, general, and admit precise analyses with testable conditions for optimality for large i.i.d. transforms $\mathbf{A}$. However, the algorithms can easily diverge for general $\mathbf{A}$. This paper presents a convergent approach to the generalized AMP (GAMP) algorithm based on direct minimization of a large-system limit approximation of the Bethe Free Energy (LSL-BFE). The proposed method uses a double-loop procedure, where the outer loop successively linearizes the LSL-BFE and the inner loop minimizes the linearized LSL-BFE using the Alternating Direction Method of Multipliers (ADMM). The proposed method, called ADMM-GAMP, is similar in structure to the original GAMP method, but with an additional least-squares minimization. It is shown that for strictly convex, smooth penalties, ADMM-GAMP is guaranteed to converge to a local minima of the LSL-BFE, thus providing a convergent alternative to GAMP that is stable under arbitrary transforms. Simulations are also presented that demonstrate the robustness of the method for non-convex penalties as well.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Onsager-corrected deep learning for sparse linear inverse problems

Deep learning has gained great popularity due to its widespread success on many inference problems. We consider the application of deep learning to the sparse linear inverse problem encountered in compressive sensing, where one seeks to recover a sparse signal from a small number of noisy linear measurements. In this paper, we propose a novel neural-network architecture that decouples prediction errors across layers in the same way that the approximate message passing (AMP) algorithm decouples them across iterations: through Onsager correction. Numerical experiments suggest that our "learned AMP" network significantly improves upon Gregor and LeCun's "learned ISTA" network in both accuracy and complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Phase diagram of matrix compressed sensing

In the problem of matrix compressed sensing we aim to recover a low-rank matrix from few of its element-wise linear projections. In this contribution we analyze the asymptotic performance of a Bayes-optimal inference procedure for a model where the matrix to be recovered is a product of random matrices. The results that we obtain using the replica method describe the state evolution of the recently introduced P-BiG-AMP algorithm. We show the existence of different types of phase transitions, their implications for the solvability of the problem, and we compare the results of the theoretical analysis to the performance reached by P-BiG-AMP. Remarkably the asymptotic replica equations for matrix compressed sensing are the same as those for a related but formally different problem of matrix factorization.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sparse Multinomial Logistic Regression via Approximate Message Passing

For the problem of multi-class linear classification and feature selection, we propose approximate message passing approaches to sparse multinomial logistic regression (MLR). First, we propose two algorithms based on the Hybrid Generalized Approximate Message Passing (HyGAMP) framework: one finds the maximum a posteriori (MAP) linear classifier and the other finds an approximation of the test-error-rate minimizing linear classifier. Then we design computationally simplified variants of these two algorithms. Next, we detail methods to tune the hyperparameters of their assumed statistical models using Stein's unbiased risk estimate (SURE) and expectation-maximization (EM), respectively. Finally, using both synthetic and real-world datasets, we demonstrate improved error-rate and runtime performance relative to existing state-of-the-art approaches to sparse MLR.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Vector Approximate Message Passing for the Generalized Linear Model

The generalized linear model (GLM), where a random vector $\boldsymbol{x}$ is observed through a noisy, possibly nonlinear, function of a linear transform output $\boldsymbol{z}=\boldsymbol{Ax}$, arises in a range of applications such as robust regression, binary classification, quantized compressed sensing, phase retrieval, photon-limited imaging, and inference from neural spike trains. When $\boldsymbol{A}$ is large and i.i.d. Gaussian, the generalized approximate message passing (GAMP) algorithm is an efficient means of MAP or marginal inference, and its performance can be rigorously characterized by a scalar state evolution. For general $\boldsymbol{A}$, though, GAMP can misbehave. Damping and sequential-updating help to robustify GAMP, but their effects are limited. Recently, a "vector AMP" (VAMP) algorithm was proposed for additive white Gaussian noise channels. VAMP extends AMP's guarantees from i.i.d. Gaussian $\boldsymbol{A}$ to the larger class of rotationally invariant $\boldsymbol{A}$. In this paper, we show how VAMP can be extended to the GLM. Numerical experiments show that the proposed GLM-VAMP is much more robust to ill-conditioning in $\boldsymbol{A}$ than damped GAMP.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Survey of Stochastic Simulation and Optimization Methods in Signal Processing

Modern signal processing (SP) methods rely very heavily on probability and statistics to solve challenging SP problems. SP methods are now expected to deal with ever more complex models, requiring ever more sophisticated computational inference techniques. This has driven the development of statistical SP methods based on stochastic simulation and optimization. Stochastic simulation and optimization algorithms are computationally intensive tools for performing statistical inference in models that are analytically intractable and beyond the scope of deterministic inference methods. They have been recently successfully applied to many difficult problems involving complex statistical models and sophisticated (often Bayesian) statistical inference techniques. This survey paper offers an introduction to stochastic simulation and optimization methods in signal and image processing. The paper addresses a variety of high-dimensional Markov chain Monte Carlo (MCMC) methods as well as deterministic surrogate methods, such as variational Bayes, the Bethe approach, belief and expectation propagation and approximate message passing algorithms. It also discusses a range of optimization methods that have been adopted to solve stochastic problems, as well as stochastic methods for deterministic optimization. Subsequently, areas of overlap between simulation and optimization, in particular optimization-within-MCMC and MCMC-driven optimization are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Hyperspectral Unmixing via Turbo Bilinear Approximate Message Passing

The goal of hyperspectral unmixing is to decompose an electromagnetic spectral dataset measured over M spectral bands and T pixels into N constituent material spectra (or "end-members") with corresponding spatial abundances. In this paper, we propose a novel approach to hyperspectral unmixing based on loopy belief propagation (BP) that enables the exploitation of spectral coherence in the endmembers and spatial coherence in the abundances. In particular, we partition the factor graph into spectral coherence, spatial coherence, and bilinear subgraphs, and pass messages between them using a "turbo" approach. To perform message passing within the bilinear subgraph, we employ the bilinear generalized approximate message passing algorithm (BiG-AMP), a recently proposed belief-propagation-based approach to matrix factorization. Furthermore, we propose an expectation-maximization (EM) strategy to tune the prior parameters and a model-order selection strategy to select the number of materials N. Numerical experiments conducted with both synthetic and real-world data show favorable unmixing performance relative to existing methods.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Iteratively Reweighted $\ell_1$ Approaches to Sparse Composite Regularization

Motivated by the observation that a given signal $\boldsymbol{x}$ admits sparse representations in multiple dictionaries $\boldsymbolΨ_d$ but with varying levels of sparsity across dictionaries, we propose two new algorithms for the reconstruction of (approximately) sparse signals from noisy linear measurements. Our first algorithm, Co-L1, extends the well-known lasso algorithm from the L1 regularizer $\|\boldsymbol{Ψx}\|_1$ to composite regularizers of the form $\sum_d λ_d \|\boldsymbolΨ_d \boldsymbol{x}\|_1$ while self-adjusting the regularization weights $λ_d$. Our second algorithm, Co-IRW-L1, extends the well-known iteratively reweighted L1 algorithm to the same family of composite regularizers. We provide several interpretations of both algorithms: i) majorization-minimization (MM) applied to a non-convex log-sum-type penalty, ii) MM applied to an approximate $\ell_0$-type penalty, iii) MM applied to Bayesian MAP inference under a particular hierarchical prior, and iv) variational expectation-maximization (VEM) under a particular prior with deterministic unknown parameters. A detailed numerical study suggests that our proposed algorithms yield significantly improved recovery SNR when compared to their non-composite L1 and IRW-L1 counterparts.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parametric Bilinear Generalized Approximate Message Passing

We propose a scheme to estimate the parameters $b_i$ and $c_j$ of the bilinear form $z_m=\sum_{i,j} b_i z_m^{(i,j)} c_j$ from noisy measurements $\{y_m\}_{m=1}^M$, where $y_m$ and $z_m$ are related through an arbitrary likelihood function and $z_m^{(i,j)}$ are known. Our scheme is based on generalized approximate message passing (G-AMP): it treats $b_i$ and $c_j$ as random variables and $z_m^{(i,j)}$ as an i.i.d.\ Gaussian 3-way tensor in order to derive a tractable simplification of the sum-product algorithm in the large-system limit. It generalizes previous instances of bilinear G-AMP, such as those that estimate matrices $\boldsymbol{B}$ and $\boldsymbol{C}$ from a noisy measurement of $\boldsymbol{Z}=\boldsymbol{BC}$, allowing the application of AMP methods to problems such as self-calibration, blind deconvolution, and matrix compressive sensing. Numerical experiments confirm the accuracy and computational efficiency of the proposed approach.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm

The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of $x$ observed from a noisy version of the transform coefficients $z = Ax$. In fact, for large zero-mean i.i.d sub-Gaussian $A$, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic $A$, however, GAMP may diverge. In this paper, we propose adaptive damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned $A$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals

We propose two novel approaches to the recovery of an (approximately) sparse signal from noisy linear measurements in the case that the signal is a priori known to be non-negative and obey given linear equality constraints, such as simplex signals. This problem arises in, e.g., hyperspectral imaging, portfolio optimization, density estimation, and certain cases of compressive imaging. Our first approach solves a linearly constrained non-negative version of LASSO using the max-sum version of the generalized approximate message passing (GAMP) algorithm, where we consider both quadratic and absolute loss, and where we propose a novel approach to tuning the LASSO regularization parameter via the expectation maximization (EM) algorithm. Our second approach is based on the sum-product version of the GAMP algorithm, where we propose the use of a Bernoulli non-negative Gaussian-mixture signal prior and a Laplacian likelihood, and propose an EM-based approach to learning the underlying statistical parameters. In both approaches, the linear equality constraints are enforced by augmenting GAMP's generalized-linear observation model with noiseless pseudo-measurements. Extensive numerical experiments demonstrate the state-of-the-art performance of our proposed approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bilinear Generalized Approximate Message Passing

We extend the generalized approximate message passing (G-AMP) approach, originally proposed for high-dimensional generalized-linear regression in the context of compressive sensing, to the generalized-bilinear case, which enables its application to matrix completion, robust PCA, dictionary learning, and related matrix-factorization problems. In the first part of the paper, we derive our Bilinear G-AMP (BiG-AMP) algorithm as an approximation of the sum-product belief propagation algorithm in the high-dimensional limit, where central-limit theorem arguments and Taylor-series approximations apply, and under the assumption of statistically independent matrix entries with known priors. In addition, we propose an adaptive damping mechanism that aids convergence under finite problem sizes, an expectation-maximization (EM)-based method to automatically tune the parameters of the assumed priors, and two rank-selection strategies. In the second part of the paper, we discuss the specializations of EM-BiG-AMP to the problems of matrix completion, robust PCA, and dictionary learning, and present the results of an extensive empirical study comparing EM-BiG-AMP to state-of-the-art algorithms on each problem. Our numerical results, using both synthetic and real-world datasets, demonstrate that EM-BiG-AMP yields excellent reconstruction accuracy (often best in class) while maintaining competitive runtimes and avoiding the need to tune algorithmic parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing

For the problem of binary linear classification and feature selection, we propose algorithmic approaches to classifier design based on the generalized approximate message passing (GAMP) algorithm, recently proposed in the context of compressive sensing. We are particularly motivated by problems where the number of features greatly exceeds the number of training examples, but where only a few features suffice for accurate classification. We show that sum-product GAMP can be used to (approximately) minimize the classification error rate and max-sum GAMP can be used to minimize a wide variety of regularized loss functions. Furthermore, we describe an expectation-maximization (EM)-based scheme to learn the associated model parameters online, as an alternative to cross-validation, and we show that GAMP's state-evolution framework can be used to accurately predict the misclassification rate. Finally, we present a detailed numerical study to confirm the accuracy, speed, and flexibility afforded by our GAMP-based approaches to binary linear classification and feature selection.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Compressive Phase Retrieval via Generalized Approximate Message Passing

In phase retrieval, the goal is to recover a signal $\mathbf{x}\in\mathbb{C}^N$ from the magnitudes of linear measurements $\mathbf{Ax}\in\mathbb{C}^M$. While recent theory has established that $M\approx 4N$ intensity measurements are necessary and sufficient to recover generic $\mathbf{x}$, there is great interest in reducing the number of measurements through the exploitation of sparse $\mathbf{x}$, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. Our experiments suggest that approximately $M\geq 2K\log_2(N/K)$ intensity measurements suffice to recover $K$-sparse Bernoulli-Gaussian signals for $\mathbf{A}$ with i.i.d Gaussian entries and $K\ll N$. Meanwhile, when recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements at 30~dB measurement SNR, PR-GAMP achieved an output SNR of no less than 28~dB in all of 100 random trials, with a median runtime of only 7.3 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, our experiments suggest that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the sparsity and problem dimensions increase.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Generalized Approximate Message Passing for Cosparse Analysis Compressive Sensing

In cosparse analysis compressive sensing (CS), one seeks to estimate a non-sparse signal vector from noisy sub-Nyquist linear measurements by exploiting the knowledge that a given linear transform of the signal is cosparse, i.e., has sufficiently many zeros. We propose a novel approach to cosparse analysis CS based on the generalized approximate message passing (GAMP) algorithm. Unlike other AMP-based approaches to this problem, ours works with a wide range of analysis operators and regularizers. In addition, we propose a novel $\ell_0$-like soft-thresholder based on MMSE denoising for a spike-and-slab distribution with an infinite-variance slab. Numerical demonstrations on synthetic and practical datasets demonstrate advantages over existing AMP-based, greedy, and reweighted-$\ell_1$ approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

In-Band Full-Duplex Wireless: Challenges and Opportunities

In-band full-duplex (IBFD) operation has emerged as an attractive solution for increasing the throughput of wireless communication systems and networks. With IBFD, a wireless terminal is allowed to transmit and receive simultaneously in the same frequency band. This tutorial paper reviews the main concepts of IBFD wireless. Because one the biggest practical impediments to IBFD operation is the presence of self-interference, i.e., the interference caused by an IBFD node's own transmissions to its desired receptions, this tutorial surveys a wide range of IBFD self-interference mitigation techniques. Also discussed are numerous other research challenges and opportunities in the design and analysis of IBFD wireless systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Factor Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments

We propose a novel receiver for orthogonal frequency division multiplexing (OFDM) transmissions in impulsive noise environments. Impulsive noise arises in many modern wireless and wireline communication systems, such as Wi-Fi and powerline communications, due to uncoordinated interference that is much stronger than thermal noise. We first show that the bit-error-rate optimal receiver jointly estimates the propagation channel coefficients, the noise impulses, the finite-alphabet symbols, and the unknown bits. We then propose a near-optimal yet computationally tractable approach to this joint estimation problem using loopy belief propagation. In particular, we merge the recently proposed "generalized approximate message passing" (GAMP) algorithm with the forward-backward algorithm and soft-input soft-output decoding using a "turbo" approach. Numerical results indicate that the proposed receiver drastically outperforms existing receivers under impulsive noise and comes within 1 dB of the matched-filter bound. Meanwhile, with N tones, the proposed factor-graph-based receiver has only O(N log N) complexity, and it can be parallelized.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing

In this work the dynamic compressive sensing (CS) problem of recovering sparse, correlated, time-varying signals from sub-Nyquist, non-adaptive, linear measurements is explored from a Bayesian perspective. While there has been a handful of previously proposed Bayesian dynamic CS algorithms in the literature, the ability to perform inference on high-dimensional problems in a computationally efficient manner remains elusive. In response, we propose a probabilistic dynamic CS signal model that captures both amplitude and support correlation structure, and describe an approximate message passing algorithm that performs soft signal estimation and support detection with a computational complexity that is linear in all problem dimensions. The algorithm, DCS-AMP, can perform either causal filtering or non-causal smoothing, and is capable of learning model parameters adaptively from the data through an expectation-maximization learning procedure. We provide numerical evidence that DCS-AMP performs within 3 dB of oracle bounds on synthetic data under a variety of operating conditions. We further describe the result of applying DCS-AMP to two real dynamic CS datasets, as well as a frequency estimation task, to bolster our claim that DCS-AMP is capable of offering state-of-the-art performance and speed on real-world high-dimensional problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Expectation-Maximization Gaussian-Mixture Approximate Message Passing

When recovering a sparse signal from noisy compressive linear measurements, the distribution of the signal's non-zero coefficients can have a profound effect on recovery mean-squared error (MSE). If this distribution was apriori known, then one could use computationally efficient approximate message passing (AMP) techniques for nearly minimum MSE (MMSE) recovery. In practice, though, the distribution is unknown, motivating the use of robust algorithms like LASSO---which is nearly minimax optimal---at the cost of significantly larger MSE for non-least-favorable distributions. As an alternative, we propose an empirical-Bayesian technique that simultaneously learns the signal distribution while MMSE-recovering the signal---according to the learned distribution---using AMP. In particular, we model the non-zero distribution as a Gaussian mixture, and learn its parameters through expectation maximization, using AMP to implement the expectation step. Numerical experiments on a wide range of signal classes confirm the state-of-the-art performance of our approach, in both reconstruction error and runtime, in the high-dimensional regime, for most (but not all) sensing operators.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem

In this work, a Bayesian approximate message passing algorithm is proposed for solving the multiple measurement vector (MMV) problem in compressive sensing, in which a collection of sparse signal vectors that share a common support are recovered from undersampled noisy measurements. The algorithm, AMP-MMV, is capable of exploiting temporal correlations in the amplitudes of non-zero coefficients, and provides soft estimates of the signal vectors as well as the underlying support. Central to the proposed approach is an extension of recently developed approximate message passing techniques to the amplitude-correlated MMV setting. Aided by these techniques, AMP-MMV offers a computational complexity that is linear in all problem dimensions. In order to allow for automatic parameter tuning, an expectation-maximization algorithm that complements AMP-MMV is described. Finally, a detailed numerical study demonstrates the power of the proposed approach and its particular suitability for application to high-dimensional problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Full-Duplex MIMO Relaying: Achievable Rates under Limited Dynamic Range

In this paper we consider the problem of full-duplex multiple-input multiple-output (MIMO) relaying between multi-antenna source and destination nodes. The principal difficulty in implementing such a system is that, due to the limited attenuation between the relay's transmit and receive antenna arrays, the relay's outgoing signal may overwhelm its limited-dynamic-range input circuitry, making it difficult---if not impossible---to recover the desired incoming signal. While explicitly modeling transmitter/receiver dynamic-range limitations and channel estimation error, we derive tight upper and lower bounds on the end-to-end achievable rate of decode-and-forward-based full-duplex MIMO relay systems, and propose a transmission scheme based on maximization of the lower bound. The maximization requires us to (numerically) solve a nonconvex optimization problem, for which we detail a novel approach based on bisection search and gradient projection. To gain insights into system design tradeoffs, we also derive an analytic approximation to the achievable rate and numerically demonstrate its accuracy. We then study the behavior of the achievable rate as a function of signal-to-noise ratio, interference-to-noise ratio, transmitter/receiver dynamic range, number of antennas, and training length, using optimized half-duplex signaling as a baseline.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Performance Bounds and Associated Design Principles for Multi-Cellular Wireless OFDMA Systems (with Detailed Proofs)

In this paper, we consider the downlink of large-scale multi-cellular OFDMA-based networks and study performance bounds of the system as a function of the number of users $K$, the number of base-stations $B$, and the number of resource-blocks $N$. Here, a resource block is a collection of subcarriers such that all such collections, that are disjoint have associated independently fading channels. We derive novel upper and lower bounds on the sum-utility for a general spatial geometry of base stations, a truncated path loss model, and a variety of fading models (Rayleigh, Nakagami-$m$, Weibull, and LogNormal). We also establish the associated scaling laws and show that, in the special case of fixed number of resource blocks, a grid-based network of base stations, and Rayleigh-fading channels, the sum information capacity of the system scales as $Θ(B \log\log K/B)$ for extended networks, and as $O(B \log\log K)$ and $Ω(\log \log K)$ for dense networks. Interpreting these results, we develop some design principles for the service providers along with some guidelines for the regulators in order to achieve provisioning of various QoS guarantees for the end users and, at the same time, maximize revenue for the service providers.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels

We propose a factor-graph-based approach to joint channel-estimation-and-decoding (JCED) of bit- interleaved coded orthogonal frequency division multiplexing (BICM-OFDM). In contrast to existing designs, ours is capable of exploiting not only sparsity in sampled channel taps but also clustering among the large taps, behaviors which are known to manifest at larger communication bandwidths. In order to exploit these channel-tap structures, we adopt a two-state Gaussian mixture prior in conjunction with a Markov model on the hidden state. For loopy belief propagation, we exploit a "generalized approximate message passing" (GAMP) algorithm recently developed in the context of compressed sensing, and show that it can be successfully coupled with soft-input soft-output decoding, as well as hidden Markov inference, through the standard sum-product framework. For N subcarriers and any channel length L < N, the resulting JCED-GAMP scheme has a computational complexity of only O(N log2 N + N|S|), where |S| is the constellation size. Numerical experiments using IEEE 802.15.4a channels show that our scheme yields BER performance within 1 dB of the known-channel bound and 3-4 dB better than soft equalization based on LMMSE and LASSO.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Belief-propagation-based joint channel estimation and decoding for spectrally efficient communication over unknown sparse channels

We consider spectrally-efficient communication over a Rayleigh N-block-fading channel with a K- sparse L-length discrete-time impulse response (for 0<K<L<N), where neither the transmitter nor receiver know the channel's coefficients nor its support. Since the high-SNR ergodic capacity of this channel has been shown to obey C(SNR) = (1-K/N)log2(SNR)+O(1), any pilot-aided scheme that sacrifices more than K dimensions per fading block to pilots will be spectrally inefficient. This causes concern about the conventional "compressed channel sensing" approach, which uses O(K polylog L) pilots. In this paper, we demonstrate that practical spectrally-efficient communication is indeed possible. For this, we propose a novel belief-propagation-based reception scheme to use with a standard bit- interleaved coded orthogonal frequency division multiplexing (OFDM) transmitter. In particular, we leverage the "relaxed belief propagation" methodology, which allows us to perform joint sparse-channel estimation and data decoding with only O(LN) complexity. Empirical results show that our receiver achieves the desired capacity pre-log factor of 1 - K/N and performs near genie-aided bounds at both low and high SNR.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior

We propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2D wavelet transform coefficients of natural images. Like other recent works, we model wavelet structure using a hidden Markov tree (HMT) but, unlike other works, ours is based on loopy belief propagation (LBP). For LBP, we adopt a recently proposed "turbo" message passing schedule that alternates between exploitation of HMT structure and exploitation of compressive-measurement structure. For the latter, we leverage Donoho, Maleki, and Montanari's recently proposed approximate message passing (AMP) algorithm. Experiments with a large image database suggest that, relative to existing schemes, our turbo LBP approach yields state-of-the-art reconstruction performance with substantial reduction in complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Joint Scheduling and Resource Allocation in OFDMA Downlink Systems via ACK/NAK Feedback

In this paper, we consider the problem of joint scheduling and resource allocation in the OFDMA downlink, with the goal of maximizing an expected long-term goodput-based utility subject to an instantaneous sum-power constraint, and where the feedback to the base station consists only of ACK/NAKs from recently scheduled users. We first establish that the optimal solution is a partially observable Markov decision process (POMDP), which is impractical to implement. In response, we propose a greedy approach to joint scheduling and resource allocation that maintains a posterior channel distribution for every user, and has only polynomial complexity. For frequency-selective channels with Markov time-variation, we then outline a recursive method to update the channel posteriors, based on the ACK/NAK feedback, that is made computationally efficient through the use of particle filtering. To gauge the performance of our greedy approach relative to that of the optimal POMDP, we derive a POMDP performance upper-bound. Numerical experiments show that, for slowly fading channels, the performance of our greedy scheme is relatively close to the upper bound, and much better than fixed-power random user scheduling (FP-RUS), despite its relatively low complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Joint Scheduling and Resource Allocation in the OFDMA Downlink: Utility Maximization under Imperfect Channel-State Information

We consider the problem of simultaneous user-scheduling, power-allocation, and rate-selection in an OFDMA downlink, with the goal of maximizing expected sum-utility under a sum-power constraint. In doing so, we consider a family of generic goodput-based utilities that facilitate, e.g., throughput-based pricing, quality-of-service enforcement, and/or the treatment of practical modulation-and-coding schemes (MCS). Since perfect knowledge of channel state information (CSI) may be difficult to maintain at the base-station, especially when the number of users and/or subchannels is large, we consider scheduling and resource allocation under imperfect CSI, where the channel state is described by a generic probability distribution. First, we consider the "continuous" case where multiple users and/or code rates can time-share a single OFDMA subchannel and time slot. This yields a non-convex optimization problem that we convert into a convex optimization problem and solve exactly using a dual optimization approach. Second, we consider the "discrete" case where only a single user and code rate is allowed per OFDMA subchannel per time slot. For the mixed-integer optimization problem that arises, we discuss the connections it has with the continuous case and show that it can solved exactly in some situations. For the other situations, we present a bound on the optimality gap. For both cases, we provide algorithmic implementations of the obtained solution. Finally, we study, numerically, the performance of the proposed algorithms under various degrees of CSI uncertainty, utilities, and OFDMA system configurations. In addition, we demonstrate advantages relative to existing state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Multiuser Scheduling in a Markov-modeled Downlink using Randomly Delayed ARQ Feedback

We focus on the downlink of a cellular system, which corresponds to the bulk of the data transfer in such wireless systems. We address the problem of opportunistic multiuser scheduling under imperfect channel state information, by exploiting the memory inherent in the channel. In our setting, the channel between the base station and each user is modeled by a two-state Markov chain and the scheduled user sends back an ARQ feedback signal that arrives at the scheduler with a random delay that is i.i.d across users and time. The scheduler indirectly estimates the channel via accumulated delayed-ARQ feedback and uses this information to make scheduling decisions. We formulate a throughput maximization problem as a partially observable Markov decision process (POMDP). For the case of two users in the system, we show that a greedy policy is sum throughput optimal for any distribution on the ARQ feedback delay. For the case of more than two users, we prove that the greedy policy is suboptimal and demonstrate, via numerical studies, that it has near optimal performance. We show that the greedy policy can be implemented by a simple algorithm that does not require the statistics of the underlying Markov channel or the ARQ feedback delay, thus making it robust against errors in system parameter estimation. Establishing an equivalence between the two-user system and a genie-aided system, we obtain a simple closed form expression for the sum capacity of the Markov-modeled downlink. We further derive inner and outer bounds on the capacity region of the Markov-modeled downlink and tighten these bounds for special cases of the system parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Communication over Unknown Sparse Frequency-Selective Block-Fading Channels

This paper considers the problem of reliable communication over discrete-time channels whose impulse responses have length $L$ and exactly $S\leq L$ non-zero coefficients, and whose support and coefficients remain fixed over blocks of $N>L$ channel uses but change independently from block to block. Here, it is assumed that the channel's support and coefficient realizations are both unknown, although their statistics are known. Assuming Gaussian non-zero-coefficients and noise, and focusing on the high-SNR regime, it is first shown that the ergodic noncoherent channel capacity has pre-log factor $1-\frac{S}{N}$ for any $L$. It is then shown that, to communicate with arbitrarily small error probability at rates in accordance with the capacity pre-log factor, it suffices to use pilot-aided orthogonal frequency-division multiplexing (OFDM) with $S$ pilots per fading block, in conjunction with an appropriate noncoherent decoder. Since the achievability result is proven using a noncoherent decoder whose complexity grows exponentially in the number of fading blocks $K$, a simpler decoder, based on $S+1$ pilots, is also proposed. Its $ε$-achievable rate is shown to have pre-log factor equal to $1-\frac{S+1}{N}$ with the previously considered channel, while its achievable rate is shown to have pre-log factor $1-\frac{S+1}{N}$ when the support of the block-fading channel remains fixed over time.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Robust Rate-Adaptive Wireless Communication Using ACK/NAK-Feedback

To combat the detrimental effects of the variability in wireless channels, we consider cross-layer rate adaptation based on limited feedback. In particular, based on limited feedback in the form of link-layer acknowledgements (ACK) and negative acknowledgements (NAK), we maximize the physical-layer transmission rate subject to an upper bound on the expected packet error rate. \textr{We take a robust approach in that we do not assume} any particular prior distribution on the channel state. We first analyze the fundamental limitations of such systems and derive an upper bound on the achievable rate for signaling schemes based on uncoded QAM and random Gaussian ensembles. We show that, for channel estimation based on binary ACK/NAK feedback, it may be preferable to use a separate training sequence at high error rates, rather than to exploit low-error-rate data packets themselves. We also develop an adaptive recursive estimator, which is provably asymptotically optimal and asymptotically efficient.

0 citations0 reviewsNo code linkedOpen access