We study the problem of detecting a random walk on a graph from a sequence of noisy measurements at every node. There are two hypotheses: either every observation is just meaningless zero-mean Gaussian noise, or at each time step exactly one node has an elevated mean, with its location following a random walk on the graph over time. We want to exploit knowledge of the graph structure and random walk parameters (specified by a Markov chain transition matrix) to detect a possibly very weak signal. The optimal detector is easily derived, and we focus on the harder problem of characterizing its performance through the (type-II) error exponent: the decay rate of the miss probability under a false alarm constraint.

The expression for the error exponent resembles the free energy of a spin glass in statistical physics, and we borrow techniques from that field to develop a lower bound. Our fully rigorous analysis uses large deviations theory to show that the lower bound exhibits a phase transition: strong performance is only guaranteed when the signal-to-noise ratio exceeds twice the entropy rate of the random walk.

Monte Carlo simulations show that the lower bound fully captures the behavior of the true exponent.

We study a spectral initialization method that serves as a key ingredient in recent work on using efficient iterative algorithms for estimating signals in nonconvex settings. Unlike previous analysis in the literature, which is restricted to the phase retrieval setting and which provides only performance bounds, we consider arbitrary generalized linear sensing models and present a precise asymptotic characterization of the performance of the spectral method in the high-dimensional regime. Our analysis reveals a phase transition phenomenon that depends on the sampling ratio. When the ratio is below a minimum threshold, the estimates given by the spectral method are no better than a random guess drawn uniformly from the hypersphere; above a maximum threshold, however, the estimates become increasingly aligned with the target signal. The computational complexity of the spectral method is also markedly different in the two phases. Worked examples and numerical results are provided to illustrate and verify the analytical predictions. In particular, simulations show that our asymptotic formulas provide accurate predictions even at moderate signal dimensions.

%B Information and Inference: A Journal of the IMA %V 9 %P 507-541 %G eng %U https://arxiv.org/abs/1702.06435 %N 3 %0 Conference Paper %B Conference on Neural Information Processing Systems (NeurIPS) %D 2020 %T Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization %A B. Aubin %A Lu, Y.M. %A F. Krzakala %A L. Zdeboravá %X We consider a commonly studied supervised classification of a synthetic dataset whose labels are generated by feeding a one-layer neural network with random iid inputs. We study the generalization performances of standard classifiers in the high-dimensional regime where α=n/d is kept finite in the limit of a high dimension d and number of samples n. Our contribution is three-fold: First, we prove a formula for the generalization error achieved by ℓ2 regularized classifiers that minimize a convex loss. This formula was first obtained by the heuristic replica method of statistical physics. Secondly, focussing on commonly used loss functions and optimizing the ℓ2 regularization strength, we observe that while ridge regression performance is poor, logistic and hinge regression are surprisingly able to approach the Bayes-optimal generalization error extremely closely. As α→∞ they lead to Bayes-optimal rates, a fact that does not follow from predictions of margin-based generalization error bounds. Third, we design an optimal loss and regularizer that provably leads to Bayes-optimal generalization error. %B Conference on Neural Information Processing Systems (NeurIPS) %8 2020 %G eng %U https://arxiv.org/abs/2006.06560 %0 Conference Paper %B International Conference on Machine Learning (ICML) %D 2020 %T The role of regularization in classification of high-dimensional noisy Gaussian mixture %A F. Mignacco %A F. Krzakala %A Yue M. Lu %A L. Zdeboravá %X We consider a high-dimensional mixture of two Gaussians in the noisy regime where even an oracle knowing the centers of the clusters misclassifies a small but finite fraction of the points. We provide a rigorous analysis of the generalization error of regularized convex classifiers, including ridge, hinge and logistic regression, in the high-dimensional limit where the number n of samples and their dimension d go to infinity while their ratio is fixed to α=n/d. We discuss surprising effects of the regularization that in some cases allows to reach the Bayes-optimal performances. We also illustrate the interpolation peak at low regularization, and analyze the role of the respective sizes of the two clusters. %B International Conference on Machine Learning (ICML) %G eng %U https://arxiv.org/abs/2002.11544 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2019 %T Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval %A Wangyu Luo %A Wael Alghamdi %A Yue M. Lu %XWe present the optimal design of a spectral method widely used to initialize nonconvex optimization algorithms for solving phase retrieval and other signal recovery problems. Our work leverages recent results that provide an exact characterization of the performance of the spectral method in the high-dimensional limit. This characterization allows us to map the task of optimal design to a constrained optimization problem in a weighted $L^2$ function space. The latter has a closed-form solution. Interestingly, under a mild technical condition, our results show that there exists a fixed design that is uniformly optimal over all sampling ratios. Numerical simulations demonstrate the performance improvement brought by the proposed optimal design over existing constructions in the literature. In a recent work, Mondelli and Montanari have shown the existence of a weak reconstruction threshold below which the spectral method cannot provide useful estimates. Our results serve to complement that work by deriving the fundamental limit of the spectral method beyond the aforementioned threshold.

%B IEEE Transactions on Signal Processing %V 67 %P 2347-2356 %G eng %U https://arxiv.org/abs/1811.04420 %N 9 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2019 %T Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview %A Yuejie Chi %A Yue M. Lu %A Yuxin Chen %XSubstantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently.

In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, robust principal component analysis, phase synchronization, and joint alignment. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated thinking of optimization and statistics leads to fruitful research findings.

%B IEEE Transactions on Signal Processing %V 67 %P 5239-5269 %G eng %U https://arxiv.org/abs/1809.09573 %N 20 %0 Journal Article %J Journal of Statistical Mechanics (Special Issue on Machine Learning) %D 2019 %T The scaling limit of high-dimensional online independent component analysis %A Wang, C. %A Lu, Y.M. %X We analyze the dynamics of an online algorithm for independent component analysis in the high-dimensional scaling limit. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measure of the target feature vector and the estimates provided by the algorithm will converge weakly to a deterministic measured-valued process that can be characterized as the unique solution of a nonlinear PDE. Numerical solutions of this PDE, which involves two spatial variables and one time variable, can be efficiently obtained. These solutions provide detailed information about the performance of the ICA algorithm, as many practical performance metrics are functionals of the joint empirical measures. Numerical simulations show that our asymptotic analysis is accurate even for moderate dimensions. In addition to providing a tool for understanding the performance of the algorithm, our PDE analysis also provides useful insight. In particular, in the high-dimensional limit, the original coupled dynamics associated with the algorithm will be asymptotically 'decoupled', with each coordinate independently solving a 1D effective minimization problem via stochastic gradient descent. Exploiting this insight to design new algorithms for achieving optimal trade-offs between computational and statistical efficiency may prove an interesting line of future research. %B Journal of Statistical Mechanics (Special Issue on Machine Learning) %V 2019 %G eng %U https://iopscience.iop.org/article/10.1088/1742-5468/ab39d6 %0 Conference Paper %B Proc. Thirty-third Conference on Neural Information Processing Systems (NeurIPS) %D 2019 %T A Solvable High-Dimensional Model of GAN %A Chuang Wang %A Hong Hu %A Yue M. Lu %X Despite the remarkable successes of generative adversarial networks (GANs) in many applications, theoretical understandings of their performance is still limited. In this paper, we present a simple shallow GAN model fed by high-dimensional input data. The dynamics of the training process of the proposed model can be exactly analyzed in the high-dimensional limit. In particular, by using the tool of scaling limits of stochastic processes, we show that the macroscopic quantities measuring the quality of the training process converge to a deterministic process that is characterized as the unique solution of a finite-dimensional ordinary differential equation (ODE). The proposed model is simple, but its training process already exhibits several different phases that can mimic the behaviors of more realistic GAN models used in practice. Specifically, depending on the choice of the learning rates, the training process can reach either a successful, a failed, or an oscillating phase. By studying the steady-state solutions of the limiting ODEs, we obtain a phase diagram that precisely characterizes the conditions under which each phase takes place. Although this work focuses on a simple GAN model, the analysis methods developed here might prove useful in the theoretical understanding of other variants of GANs with more advanced training algorithms. %B Proc. Thirty-third Conference on Neural Information Processing Systems (NeurIPS) %G eng %U https://arxiv.org/abs/1805.08349 %0 Conference Paper %B Proc. International Conference on Machine Learning (ICML) %D 2019 %T Generalized Approximate Survey Propagation for High-Dimensional Estimation %A L. Saglietti %A Lu, Y.M. %A C. Lucibello %X In Generalized Linear Estimation (GLE) problems, we seek to estimate a signal that is observed through a linear transform followed by a component-wise, possibly nonlinear and noisy, channel. In the Bayesian optimal setting, Generalized Approximate Message Passing (GAMP) is known to achieve optimal performance for GLE. However, its performance can significantly degrade whenever there is a mismatch between the assumed and the true generative model, a situation frequently encountered in practice. In this paper, we propose a new algorithm, named Generalized Approximate Survey Propagation (GASP), for solving GLE in the presence of prior or model mis-specifications. As a prototypical example, we consider the phase retrieval problem, where we show that GASP outperforms the corresponding GAMP, reducing the reconstruction threshold and, for certain choices of its parameters, approaching Bayesian optimal performance. Furthermore, we present a set of State Evolution equations that exactly characterize the dynamics of GASP in the high-dimensional limit. %B Proc. International Conference on Machine Learning (ICML) %G eng %U https://arxiv.org/abs/1905.05313 %0 Conference Paper %B Prof. International Symposium on Information Theory (ISIT) %D 2019 %T Asymptotics and optimal designs of SLOPE for sparse linear regression %A H. Hong %A Lu, Y.M. %XIn sparse linear regression, the SLOPE estimator generalizes LASSO by assigning magnitude-dependent regular- izations to different coordinates of the estimate. In this paper, we present an asymptotically exact characterization of the performance of SLOPE in the high-dimensional regime where the number of unknown parameters grows in proportion to the number of observations. Our asymptotic characterization enables us to derive optimal regularization sequences to either minimize the MSE or to maximize the power in variable selection under any given level of Type-I error. In both cases, we show that the optimal design can be recast as certain infinite-dimensional convex optimization problems, which have efficient and accurate finite-dimensional approximations. Numerical simulations verify our asymptotic predictions. They also demonstrate the superi- ority of our optimal design over LASSO and a regularization sequence previously proposed in the literature.

%B Prof. International Symposium on Information Theory (ISIT) %G eng %U https://arxiv.org/abs/1903.11582 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2019 %T Super resolution phase retrieval for sparse signals %A G. Baechler %A M. Kreković %A J. Ranieri %A A. Chebira %A Lu, Y.M. %A M. Vetterli %X In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts to recover the phase information of a signal from the magnitude of its Fourier transform to enable the reconstruction of the original signal. Solving the phase retrieval problem is equivalent to recovering a signal from its auto-correlation function. In this paper, we assume the original signal to be sparse; this is a natural assumption in many applications, such as X-ray crystallography, speckle imaging and blind channel estimation. We propose an algorithm that resolves the phase retrieval problem in three stages: i) we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, ii) we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, iii) we recover the amplitudes of the atoms given their locations and the measured auto-correlation function. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. Along with the algorithm, we derive its performance bound with a theoretical analysis and propose a set of enhancements to improve its computational complexity and noise resilience. Finally, we demonstrate the benefits of the proposed method via a comparison against Charge Flipping, a notable algorithm in crystallography. %B IEEE Transactions on Signal Processing %V 67 %G eng %U https://arxiv.org/abs/1808.01961 %N 18 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2019 %T MMSE Approximation For Sparse Coding Algorithms Using Stochastic Resonance %A Dror Simon %A Jeremias Sulam %A Yaniv Romano %A Yue M. Lu %A Michael Elad %XSparse coding refers to the pursuit of the sparsest representation of a signal in a typically overcomplete dictionary. From a Bayesian perspective, sparse coding provides a Maximum a Posteriori (MAP) estimate of the unknown vector under a sparse prior. Various nonlinear algorithms are available to approximate the solution of such problems.

In this work, we suggest enhancing the performance of sparse coding algorithms by a deliberate and controlled contamination of the input with random noise, a phenomenon known as stochastic resonance. This not only allows for increased performance, but also provides a computationally efficient approximation to the Minimum Mean Square Error (MMSE) estimator, which is ordinarily intractable to compute. We demonstrate our findings empirically and provide a theoretical analysis of our method under several different cases.

%B IEEE Transactions on Signal Processing %V 67 %G eng %U https://arxiv.org/abs/1806.10171 %N 17 %0 Journal Article %J IEEE Journal of Selected Topics in Signal Processing %D 2018 %T Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis %A Chuang Wang %A Yonina C. Eldar %A Yue M. Lu %X We present a high-dimensional analysis of three popular algorithms, namely, Oja's method, GROUSE and PETRELS, for subspace estimation from streaming and highly incomplete observations. We show that, with proper time scaling, the time-varying principal angles between the true subspace and its estimates given by the algorithms converge weakly to deterministic processes when the ambient dimension \(n\) tends to infinity. Moreover, the limiting processes can be exactly characterized as the unique solutions of certain ordinary differential equations (ODEs). A finite sample bound is also given, showing that the rate of convergence towards such limits is \(\mathcal{O}(1/\sqrt{n})\). In addition to providing asymptotically exact predictions of the dynamic performance of the algorithms, our high-dimensional analysis yields several insights, including an asymptotic equivalence between Oja's method and GROUSE, and a precise scaling relationship linking the amount of missing data to the signal-to-noise ratio. By analyzing the solutions of the limiting ODEs, we also establish phase transition phenomena associated with the steady-state performance of these techniques. %B IEEE Journal of Selected Topics in Signal Processing %V 12 %G eng %U https://arxiv.org/abs/1805.06834 %N 6 %0 Journal Article %J Proceedings of the IEEE %D 2018 %T A Modern Perspective on Streaming PCA and Subspace Tracking: The Missing Data Case %A Laura Balzano %A Yuejie Chi %A Yue M. Lu %X For many modern applications in science and engineering, data are collected in a streaming fashion carrying time-varying information, and practitioners need to process them with a limited amount of memory and computational resources in a timely manner for decision making. This often is coupled with the missing data problem, such that only a small fraction of data attributes are observed. These complications impose significant, and unconventional, constraints on the problem of streaming Principal Component Analysis (PCA) and subspace tracking, which is an essential building block for many inference tasks in signal processing and machine learning. This survey article reviews a variety of classical and recent algorithms for solving this problem with low computational and memory complexities, particularly those applicable in the big data regime with missing data. We illustrate that streaming PCA and subspace tracking algorithms can be understood through algebraic and geometric perspectives and they need to be adjusted carefully to handle missing data. Both asymptotic and non-asymptotic convergence guarantees are reviewed. Finally, we benchmark the performance of several competitive algorithms in the presence of missing data for both well-conditioned and ill-conditioned systems. %B Proceedings of the IEEE %V 106 %P 1293-1310 %8 Aug 2018 %G eng %N 8 %0 Journal Article %J IEEE Transactions on Information Theory %D 2018 %T Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis %A Yue M. Lu %A Jon Oñativia %A Pier Luigi Dragotti %XFinding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. This paper studies ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Unlike our previous work which establishes deterministic (worst-case) sparsity bounds for ProSparse to succeed, this paper presents a probabilistic average-case analysis of the algorithm. Based on a generating-function approach, closed-form expressions for the exact success probabilities of ProSparse are given. The success probabilities are also analyzed in the high-dimensional regime. This asymptotic analysis characterizes a sharp phase transition phenomenon regarding the performance of the algorithm.

%B IEEE Transactions on Information Theory %V 64 %P 2639-2647 %G eng %U https://arxiv.org/abs/1611.07971 %N 4 %0 Conference Paper %B 55th Annual Allerton Conference on Communication, Control, and Computing %D 2017 %T Phase Retrieval via Linear Programming: Fundamental Limits and Algorithmic Improvements %A Oussama Dhifallah %A Christos Thrampoulidis %A Yue M. Lu %X A recently proposed convex formulation of the phase retrieval problem estimates the unknown signal by solving a simple linear program. This new scheme, known as PhaseMax, is computationally efficient compared to standard convex relaxation methods based on lifting techniques. In this paper, we present an exact performance analysis of PhaseMax under Gaussian measurements in the large system limit. In contrast to previously known performance bounds in the literature, our results are asymptotically exact and they also reveal a sharp phase transition phenomenon. Furthermore, the geometrical insights gained from our analysis led us to a novel nonconvex formulation of the phase retrieval problem and an accompanying iterative algorithm based on successive linearization and maximization over a polytope. This new algorithm, which we call PhaseLamp, has provably superior recovery performance over the original PhaseMax method. %B 55th Annual Allerton Conference on Communication, Control, and Computing %G eng %U https://arxiv.org/abs/1710.05234 %0 Conference Paper %B Conference on Neural Information Processing Systems (NIPS) %D 2017 %T The Scaling Limit of High-Dimensional Online Independent Component Analysis %A Chuang Wang %A Yue M. Lu %XWe analyze the dynamics of an online algorithm for independent component analysis in the high-dimensional scaling limit. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measure of the target feature vector and the estimates provided by the algorithm will converge weakly to a deterministic measured-valued process that can be characterized as the unique solution of a nonlinear PDE. Numerical solutions of this PDE, which involves two spatial variables and one time variable, can be efficiently obtained. These solutions provide detailed information about the performance of the ICA algorithm, as many practical performance metrics are functionals of the joint empirical measures. Numerical simulations show that our asymptotic analysis is accurate even for moderate dimensions. In addition to providing a tool for understanding the performance of the algorithm, our PDE analysis also provides useful insight. In particular, in the high-dimensional limit, the original coupled dynamics associated with the algorithm will be asymptotically “decoupled”, with each coordinate independently solving a 1-D effective minimization problem via stochastic gradient descent. Exploiting this insight to design new algorithms for achieving optimal trade-offs between computational and statistical efficiency may prove an interesting line of future research.

%B Conference on Neural Information Processing Systems (NIPS) %8 December %G eng %0 Conference Paper %B the 7th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) %D 2017 %T Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis %A Oussama Dhifallah %A Yue M. Lu %XWe consider a recently proposed convex formulation, known as the PhaseMax method, for solving the phase retrieval problem. Using the replica method from statistical mechanics, we analyze the performance of PhaseMax in the high-dimensional limit. Our analysis predicts the exact asymptotic performance of PhaseMax. In particular, we show that a sharp phase transi- tion phenomenon takes place, with a simple analytical formula characterizing the phase transition boundary. This result shows that the oversampling ratio required by existing performance bounds in the literature can be significantly reduced. Numerical results confirm the validity of our replica analysis, showing that the theoretical predictions are in excellent agreement with the actual performance of the algorithm, even for moderate signal dimensions.

%B the 7th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) %G eng %U https://arxiv.org/pdf/1708.03355.pdf %0 Conference Paper %B IEEE International Symposium on Information Theory (ISIT) %D 2017 %T Spectral Initialization for Nonconvex Estimation: High-Dimensional Limit and Phase Transitions %A Yue M. Lu %A Gen Li %XWe study a simple spectral method that serves as a key ingredient in a growing line of work using efficient iterative algorithms for estimating signals in nonconvex settings. Unlike previous work, which focuses on the phase retrieval setting and provides only bounds on the performance, we consider arbitrary generalized linear sensing models and provide an exact characterization of the performance of the spectral method in the high-dimensional regime. Our analysis reveals a phase transition phenomenon that depends on the sampling ratio. When the ratio is below a critical threshold, the estimates given by the spectral method are no better than random guesses drawn uniformly from the hypersphere; above the threshold, however, the estimates become increasingly aligned with the underlying signal. Worked examples and numerical simulations are provided to illustrate and verify the analytical predictions.

%B IEEE International Symposium on Information Theory (ISIT) %G eng %0 Conference Paper %B Signal Processing with Adaptive Structured Representatives (SPARS) Workshop %D 2017 %T Subspace Estimation from Incomplete Observations: A Precise High-Dimensional Analysis %A Chuang Wang %A Yonina Eldar %A Yue M. Lu %XThe problem of estimating and tracking low-rank subspaces from incomplete observations has received a lot of attention recently in the signal processing and learning communities. Popular algorithms, such as GROUSE and PETRELS, are often very effective in practice, but their performance depends on the careful choice of algorithmic parameters. Important questions, such as the global convergence of these algorithms and how the noise level, subsampling ratio, and various other parameters affect the performance, are not fully understood. In this paper, we present a precise analysis of the performance of these algorithms in the asymptotic regime where the ambient dimension tends to infinity. Specifically, we show that the time-varying trajectories of estimation errors converge weakly to a deterministic function of time, which is characterized as the unique solution of a system of ordinary differential equations (ODEs.) Analyzing the limiting ODEs also reveals and characterizes sharp phase transition phenomena associated with these algorithms. Numerical simulations verify the accuracy of our asymptotic predictions, even for moderate signal dimensions.

%B Signal Processing with Adaptive Structured Representatives (SPARS) Workshop %8 5 - 8 June %G eng %0 Journal Article %J SIAM Journal on Imaging Sciences %D 2017 %T A Tale of Two Bases: Local-Nonlocal Regularization on Image Patches with Convolution Framelets %A Ruijie Yin %A Tingran Gao %A Yue M. Lu %A Ingrid Daubechies %XWe propose an image representation scheme combining the local and nonlocal characterization of patches in an image. Our representation scheme can be shown to be equivalent to a tight frame constructed from convolving local bases (e.g., wavelet frames, discrete cosine transforms, etc.) with nonlocal bases (e.g., spectral basis induced by nonlinear dimension reduction on patches), and we call the resulting frame elements convolution framelets. Insight gained from analyzing the proposed representation leads to a novel interpretation of a recent high-performance patch-based image pro- cessing algorithm using the point integral method (PIM) and the low dimensional manifold model (LDMM) [S. Osher, Z. Shi, and W. Zhu, Low Dimensional Manifold Model for Image Processing, Tech. Rep., CAM report 16-04, UCLA, Los Angeles, CA, 2016]. In particular, we show that LDMM is a weighted l2-regularization on the coefficients obtained by decomposing images into linear combinations of convolution framelets; based on this understanding, we extend the original LDMM to a reweighted version that yields further improved results. In addition, we establish the energy concentration property of convolution framelet coefficients for the setting where the local basis is constructed from a given nonlocal basis via a linear reconstruction framework; a generalization of this framework to unions of local embeddings can provide a natural setting for interpreting BM3D, one of the state-of-the-art image denoising algorithms.

%B SIAM Journal on Imaging Sciences %V 10 %P 711-750 %8 2017 %G eng %N 2 %0 Journal Article %J IEEE Transactions on Image Processing %D 2017 %T Understanding Symmetric Smoothing Filters: A Gaussian Mixture Model Perspective %A Stanley H. Chan %A Todd Zickler %A Yue M. Lu %XMany patch-based image denoising algorithms can be formulated as applying a smoothing filter to the noisy image. Expressed as matrices, the smoothing filters must be row normalized so that each row sums to unity. Surprisingly, if we apply a column normalization before the row normalization, the performance of the smoothing filter can often be significantly improved. Prior works showed that such performance gain is related to the Sinkhorn-Knopp balancing algorithm, an iterative procedure that symmetrizes a row-stochastic matrix to a doubly-stochastic matrix. However, a complete understanding of the performance gain phenomenon is still lacking.

In this paper, we study the performance gain phenomenon from a statistical learning perspective. We show that Sinkhorn-Knopp is equivalent to an Expectation-Maximization (EM) algorithm of learning a Product of Gaussians (PoG) prior of the image patches. By establishing the correspondence between the steps of Sinkhorn-Knopp and the EM algorithm, we provide a geometrical interpretation of the symmetrization process. The new PoG model also allows us to develop a new denoising algorithm called Product of Gaussian Non-Local-Means (PoG-NLM). PoG-NLM is an extension of the Sinkhorn-Knopp and is a generalization of the classical non-local means. Despite its simple formulation, PoG-NLM outperforms many existing smoothing filters and has a similar performance compared to BM3D.

%B IEEE Transactions on Image Processing %V 26 %P 5107-5121 %8 Nov 2017 %G eng %U http://arxiv.org/abs/1601.00088 %N 11 %0 Conference Paper %B IEEE Information Theory Workshop (ITW) %D 2016 %T Online Learning for Sparse PCA in High Dimensions: Exact Dynamics and Phase Transitions %A Chuang Wang %A Yue M. Lu %XWe study the dynamics of an online algorithm for learning a sparse leading eigenvector from samples generated from a spiked covariance model. This algorithm combines the classical Oja's method for online PCA with an element-wise nonlinearity at each iteration to promote sparsity. In the high-dimensional limit, the joint empirical measure of the underlying sparse eigenvector and its estimate provided by the algorithm is shown to converge weakly to a deterministic, measure-valued process. This scaling limit is characterized as the unique solution of a nonlinear PDE, and it provides exact information regarding the asymptotic performance of the algorithm. For example, performance metrics such as the cosine similarity and the misclassification rate in sparse support recovery can be obtained by examining the limiting dynamics. A steady-state analysis of the nonlinear PDE also reveals an interesting phase transition phenomenon. Although our analysis is asymptotic in nature, numerical simulations show that the theoretical predictions are accurate for moderate signal dimensions.

%B IEEE Information Theory Workshop (ITW) %8 September %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %D 2016 %T ProSparse denoise: Prony's based sparsity pattern recovery in the presence of noise %A J. Onativia %A P. L. Dragotti %A Yue M. Lu %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %8 March %G eng %0 Journal Article %J IEEE Signal Processing Letters %D 2016 %T Kaczmarz Method for Solving Quadratic Equations %A Yuejie Chi %A Yue M. Lu %XEstimating low-rank positive-semidefinite (PSD) matrices from symmetric rank-one measurements is of great importance in many applications, such as high-dimensional data processing, quantum state tomography, and phase retrieval. When the rank is known a priori, this problem can be regarded as solving a system of quadratic equations of a low-dimensional subspace. The authors develop a fast iterative algorithm based on an adaptation of the Kaczmarz method, which is traditionally used for solving overdetermined linear systems. In particular, the authors characterize the dynamics of the algorithm when the measurement vectors are composed of standard Gaussian entries in the online setting. Numerical simulations demonstrate the compelling performance of the proposed algorithm.

%B IEEE Signal Processing Letters %V 23 %P 1183-1187 %8 2016 %G eng %N 9 %0 Journal Article %J IEEE Signal Processing Letters %D 2016 %T Decomposition space-variant blur in image deconvolution %A Filip Sroubek %A Jan Kamenicky %A Yue M. Lu %XPerceptual decision-making is fundamental to a broad range of fields including neurophysiology, economics, medicine, advertising, law, etc. While recent findings have yielded major advances in our understanding of perceptual decision-making, decision-making as a function of time and frequency (i.e., decision-making dynamics) is not well understood. To limit the review length, we focus most of this review on human findings. Animal findings, which are extensively reviewed elsewhere, are included when beneficial or necessary. We attempt to put these various findings and datasets - which can appear to be unrelated in the absence of a formal dynamic analysis - into context using published models. Specifically, by adding appropriate dynamic mechanisms (e.g., high-pass filters) to existing models, it appears that a number of otherwise seemingly disparate findings from the literature might be explained. One hypothesis that arises through this dynamic analysis is that decision-making includes phasic (high-pass) neural mechanisms, an evidence accumulator and/or some sort of mid-trial decision-making mechanism (e.g., peak detector and/or decision boundary).

%B Journal of Neurophysiology %V 115 %8 2016 %G eng %U http://jn.physiology.org/content/early/2015/10/09/jn.00225.2015 %N 1 %0 Journal Article %J NeuroImage %D 2016 %T Matched Signal Detection on Graphs: Theory and Application to Brain Imaging Data Classification %A Chenhui Hu %A Jorge Sepulcre %A Keith A. Johnson %A George E. Fakhri %A Yue M. Lu %A Quangzheng Li %XWe propose a fully distributed Gauss-Newton algorithm for state estimation of electric power systems. At each Gauss-Newton iteration, matrix-splitting techniques are utilized to carry out the matrix inversion needed for calculating the Gauss-Newton step in a distributed fashion. In order to reduce the communication burden as well as increase robustness of state estimation, the proposed distributed scheme relies only on local information and a limited amount of information from neighboring areas. The matrix-splitting scheme is designed to calculate the Gauss-Newton step with exponential convergence speed. The effectiveness of the method is demonstrated in various numerical experiments.

%B IEEE Transactions on Power Systems %V 31 %P 3804-3815 %8 2016 %G eng %N 5 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2016 %T Sampling Sparse Signals on the Sphere: Algorithms and Applications %A Ivan Dokmanic %A Yue M. Lu %XWe propose a sampling scheme that can perfectly reconstruct a collection of

spikes on the sphere from samples of their lowpass-filtered observations.

Central to our algorithm is a generalization of the annihilating filter

method, a tool widely used in array signal processing and finite-rate-of-innovation

(FRI) sampling. The proposed algorithm can reconstruct $K$ spikes

from $(K+\sqrt{K})^2$ spatial samples---a sampling requirement that

improves over known sparse sampling schemes on the sphere by a factor of up

to four.

We showcase the versatility of the proposed algorithm by applying it to

three different problems: 1) sampling diffusion processes induced by

localized sources on the sphere, 2) shot-noise removal, and 3) sound source

localization (SSL) by a spherical microphone array. In particular, we show

how SSL can be reformulated as a spherical sparse sampling problem.

We study phase retrieval by using a simple non-convex algorithm based on iterative projections. Our main contribution in this work is to establish an exact analysis of the dynamics of the algorithm in an online setting, with Gaussian measurement vectors. We show that the algorithm dynamics, measured by the squared distance between the current estimate and the true solution, can be fully characterized by a 2D Markov process, irrespective of the underlying signal dimension. Furthermore, in the large systems limit (i.e., as the signal dimension tends to infinity), the random sample paths of the 2D Markov process converge to the solutions of two deterministic and coupled ordinary differential equations (ODEs). Numerical simulations verify the accuracy of our analytical predictions, even for moderate system sizes. This suggests that the ODE approach presented in this work provides an effective tool for analyzing the performance and convergence of the algorithm.

%B Allerton Conference on Communications, Control, and Computing %8 October %G eng %0 Conference Paper %B IEEE International Conference on Image Processing %D 2015 %T Understanding symmetric smoothing filters via Gaussian mixtures %A Stanley H. Chan %A Todd Zickler %A Yue M. Lu %B IEEE International Conference on Image Processing %8 September %G eng %0 Conference Paper %B Signal Processing with Adaptive Sparse Structured Representations (SPARS) Workshop %D 2015 %T Sparsity according to Prony, Average Performance Analysis %A Jon Onativia %A Pier Luigi Dragotti %A Yue M. Lu %B Signal Processing with Adaptive Sparse Structured Representations (SPARS) Workshop %C Cambridge, England %8 Jul. %G eng %0 Journal Article %J PLOS ONE %D 2015 %T A Spectral Graph Regression Model for Learning Brain Connectivity of Alzheimer's Disease %A Chenhui Hu %A Lin Cheng %A Jorge Sepulcre %A Keith A. Johnson %A Georges E. Fakhri %A Yue M. Lu %A Quanzheng Li %XUnderstanding network features of brain pathology is essential to reveal underpinnings of neurodegenerative diseases. In this paper, we introduce a novel graph regression model (GRM) for learning structural brain connectivity of Alzheimer’s disease (AD) measured by amyloid-β deposits. The proposed GRM regards 11 C-labeled Pittsburgh Compound-B (PiB) positron emission tomography (PET) imaging data as smooth signals defined on an unknown graph. This graph is then estimated through an optimization framework, which fits the graph to the data with an adjustable level of uniformity of the connection weights. Under the assumed data model, results based on simulated data illustrate that our approach can accurately reconstruct the underlying network, often with better reconstruction than those obtained by both sample correlation and ℓ1 -regularized partial correlation estimation. Evaluations performed upon PiB-PET imaging data of 30 AD and 40 elderly normal control (NC) subjects demonstrate that the connectivity patterns revealed by the GRM are easy to interpret and consistent with known pathology. Moreover, the hubs of the reconstructed networks match the cortical hubs given by functional MRI. The discriminative network features including both global connectivity measurements and degree statistics of specific nodes discovered from the AD and NC amyloid-beta networks provide new potential biomarkers for preclinical and clinical AD.

%B PLOS ONE %V 10 %8 2015 %G eng %U http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0128136 %N 5 %0 Conference Paper %B Proc. of Asilomar Conference on Signals, Systems and Computers %D 2014 %T Optimal hypothesis testing with combinatorial structure: Detecting random walks on graphs %A Ameya Agaskar %A Yue M. Lu %XSuppose we have a time series of observations for each node in a network, and we wish to detect the presence of a particle undergoing a random walk on the network. If there is no such particle, then we observe only zero-mean Gaussian noise. If present, however, the location of the particle has an elevated mean. How well can we detect the particle at low signal-to-noise ratios? This is a special case of the problem of detecting hidden Markov processes (HMPs).

The performance metric we analyze is the error exponent of the optimal detector, which measures the exponential rate of decay in the miss probability if the false alarm probability is held fixed as the observation time increases. This problem exhibits deep connections to a problem in statistical physics: computing the free energy density of a spin glass.

We develop a generalized version of the random energy model (REM) spin glass, whose free energy density provides a lower bound for our error exponent, and compute the bound using large deviations techniques. The bound closely matches empirical results in numerical experiments, and suggests a phase transition phenomenon: below a threshold SNR, the error exponent is nearly constant and near zero, indicating poor performance; above the threshold, there is rapid improvement in performance as the SNR increases. The location of the phase transition depends on the entropy rate of the Markov process.

%B Proc. of Asilomar Conference on Signals, Systems and Computers %C Pacific Grove, CA %8 Nov. %G eng %0 Conference Paper %B IEEE Global Conference on Signal and Information Processing (GlobalSIP) %D 2014 %TEfficient image reconstruction for gigapixel quantum image sensors

%A S. H. Chan %A Lu, Y.M. %XRecent advances in materials, devices and fabrication technologies have motivated a strong momentum in developing solid-state sensors that can detect individual photons in space and time. It has been envisioned that such sensors can eventually achieve very high spatial resolutions (e.g., 10^9 pixels/chip) as well as high frame rates (e.g., 10^6 frames/sec). In this paper, we present an efficient algorithm to reconstruct images from the massive binary bit-streams generated by these sensors. Based on the concept of alternating direction method of multipliers (ADMM), we transform the computationally intensive optimization problem into a sequence of subproblems, each of which has efficient implementations in the form of polyphase-domain filtering or pixel-wise nonlinear mappings. Moreover, we reformulate the original maximum likelihood estimation as maximum a posterior estimation by introducing a total variation prior. Numerical results demonstrate the strong performance of the proposed method, which achieves several dB’s of improvement in PSNR and requires a shorter runtime as compared to standard gradient-based approaches.

%B IEEE Global Conference on Signal and Information Processing (GlobalSIP) %C Atlanta, GA %8 Dec. %G eng %0 Conference Paper %B IEEE Global Conference on Signal and Information Processing (GlobalSIP) %D 2014 %TRandomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities

%A Agaskar, A. %A C Wang %A Lu, Y.M. %XThe Kaczmarz method, or the algebraic reconstruction technique (ART), is a popular method for solving large-scale overdetermined systems of equations. Recently, Strohmer et al. proposed the randomized Kaczmarz algorithm, an improvement that guarantees exponential convergence to the solution. This has spurred much interest in the algorithm and its extensions. We provide in this paper an exact formula for the mean squared error (MSE) in the value reconstructed by the algorithm. We also compute the exponential decay rate of the MSE, which we call the “annealed” error exponent. We show that the typical performance of the algorithm is far better than the average performance. We define the “quenched” error exponent to characterize the typical performance. This is far harder to compute than the annealed error exponent, but we provide an approximation that matches empirical results. We also explore optimizing the algorithm’s row-selection probabilities to speed up the algorithm’s convergence.

%B IEEE Global Conference on Signal and Information Processing (GlobalSIP) %C Atlanta, GA %8 Dec. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %D 2014 %TFinite Dimensional FRI

%A Jon Oñativia %A Yue M. Lu %A Pier Luigi Dragotti %XTraditional Finite Rate of Innovation (FRI) theory has considered the problem of sampling continuous-time signals. This framework can be naturally extended to the case where the input is a discrete-time signal. Here we present a novel approach which uses both the traditional FRI sampling scheme, based on the annihilating filter method, and the fact that in this new setup the null space of the problem to be solved is finite dimensional.

In the noiseless scenario, we show that this new approach is able to perfectly recover the original signal at the critical sampling rate. We also present simulation results in the noisy scenario where this new approach improves performances in terms of the mean squared error (MSE) of the reconstructed signal when compared to the canonical FRI algorithms and compressed sensing (CS).

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %C Florence %8 May %G eng %0 Journal Article %J IEEE Transactions on Image Processing %D 2014 %TMonte Carlo Non-Local Means: Random Sampling for Large-Scale Image Filtering

%A Stanley H. Chan %A Todd Zickler %A Yue M. Lu %XWe propose a randomized version of the non-local means (NLM) algorithm for large-scale image filtering. The new algorithm, called Monte Carlo non-local means (MCNLM), speeds up the classical NLM by computing a small subset of image patch distances, which are randomly selected according to a designed sampling pattern. We make two contributions. First, we analyze the performance of the MCNLM algorithm and show that, for large images or large external image databases, the random outcomes of MCNLM are tightly concentrated around the deterministic full NLM result. In particular, our error probability bounds show that, at any given sampling ratio, the probability for MCNLM to have a large deviation from the original NLM solution decays exponentially as the size of the image or database grows. Second, we derive explicit formulas for optimal sampling patterns that minimize the error probability bound by exploiting partial knowledge of the pairwise similarity weights. Numerical experiments show that MCNLM is competitive with other state-of-the-art fast NLM algorithms for single-image denoising. When applied to denoising images using an external database containing ten billion patches, MCNLM returns a randomized solution that is within 0.2 dB of the full NLM solution while reducing the runtime by three orders of magnitude.

%B IEEE Transactions on Image Processing %V 23 %P 3711-3725 %G eng %N 8 %0 Journal Article %J IEEE Transactions on Information Theory %D 2014 %TOn Sparse Representation in Fourier and Local Bases

%A Pier Luigi Dragotti %A Yue M. Lu %XWe consider the classical problem of finding the sparse representation of a signal in a pair of bases. When both bases are orthogonal, it is known that the sparse representation is unique when the sparsity $K$ of the signal satisfies $K<1/\mu(\mD)$, where $\mu(\mD)$ is the mutual coherence of the dictionary. Furthermore, the sparse representation can be obtained in polynomial time by Basis Pursuit (BP), when $K<0.91/\mu(\mD)$. Therefore, there is a gap between the unicity condition and the one required to use the polynomial-complexity BP formulation. For the case of general dictionaries, it is also well known that finding the sparse representation under the only constraint of unicity is NP-hard. In this paper, we introduce, for the case of Fourier and canonical bases, a polynomial complexity algorithm that finds all the possible $K$-sparse representations of a signal under the weaker condition that $K<\sqrt{2} /\mu(\mD)$. Consequently, when $K<1/\mu(\mD)$, the proposed algorithm solves the unique sparse representation problem for this structured dictionary in polynomial time. We further show that the same method can be extended to many other pairs of bases, one of which must have local atoms. Examples include the union of Fourier and local Fourier bases, the union of discrete cosine transform and canonical bases, and the union of random Gaussian and canonical bases.

%B IEEE Transactions on Information Theory %V 60 %P 7888-7899 %8 2014 %G eng %N 12 %0 Journal Article %J Geophys. J. Int. %D 2014 %TSensor Placement for the Analysis of Seismic Surface Waves: Source of Error, Design Criterion, and Array Design Algorithms

%A Stefano Maranò %A Donat Fäh %A Yue M. Lu %XSeismic surface waves can be measured by deploying an array of seismometers on the surface of the earth. The goal of such measurement surveys is, usually, to estimate the velocity of propagation and the direction of arrival of the seismic waves. In this paper, we address the issue of sensor placement for the analysis of seismic surface waves from ambient vibration wavefields. First, we explain in detail how the array geometry affects the mean-squared estimation error (MSEE) of parameters of interest, such as the velocity and direction of propagation, both at low and high signal-to-noise ratios (SNRs). Second, we propose a cost function suitable for the design of the array geometry with particular focus on the estimation of the wavenumber of both Love and Rayleigh waves. Third, we present and compare several computational approaches to minimize the proposed cost function. Numerical experiments verify the effectiveness of our cost function and resulting array geometry designs, leading to greatly improved estimation performance in comparison to arbitrary array geometries, both at low and high SNR levels.

%B Geophys. J. Int. %V 197 %P 1566-1581 %G eng %U http://gji.oxfordjournals.org/content/197/3/1566.full.pdf+html %N 3 %0 Conference Paper %B Proc. IEEE Global Conference on Signal and Information Processing %D 2013 %T A Framework for Adaptive Parameter Estimation with Finite Memory %A Yue M. Lu %X We consider the problem of estimating an unknown parameter from a finite collection of different statistical experiments. The measurements are taken sequentially. Based on the observations made so far, we adaptively select the next experiment that provides the most information about the parameter. Summarizing past information with finite memory, we present a general framework for efficient adaptive estimation, with the sensing schemes fully characterized by finite-state parametric Markov chains. We establish an analytic formula linking the asymptotic performance of adaptive estimation schemes to the steady-state distributions of the associated Markov chains. Consequently, finding optimal adaptive strategies can be reformulated as the problem of designing a (continuous) family of Markov chains with prescribed steady-state distributions.We also propose a quantitative design criterion for optimal sensing policies based on minimax ratio regret. %B Proc. IEEE Global Conference on Signal and Information Processing %C Austin, TX %8 Dec. 3 - 5 %G eng %0 Conference Paper %B Proc. IEEE Global Conference on Signal and Information Processing %D 2013 %T ALARM: A Logistic Auto-Regressive Model for binary processes on networks %A Ameya Agaskar %A Yue M. Lu %XWe introduce the ALARM model, a logistic autoregressive model for discrete-time binary processes on networks, and describe a technique for learning the graph structure underlying the model from observations. Using only a small number of parameters, the proposed ALARM can describe a wide range of dynamic behavior on graphs, such as the contact process, voter process, and even some epidemic processes. Under ALARM, at each time step, the probability of a node having value 1 is determined by the values taken by its neighbors in the past; specifically, its probability is given by the logistic function evaluated at a linear combination of its neighbors' past values (within a fixed time window) plus a bias term. We examine the behavior of this model for 1D and 2D lattice graphs, and observe a phase transition in the steady state for 2D lattices. We then study the problem of learning a graph from ALARM observations. We show how a regularizer promoting group sparsity can be used to efficiently learn the parameters of the model from a realization, and demonstrate the resulting ability to reconstruct the underlying network from the data.

%B Proc. IEEE Global Conference on Signal and Information Processing %C Austin, TX %8 Dec. 3 - 5 %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %D 2013 %T A novel compressive sensing approach to simultaneously acquire color and near-infrared images on a single sensor %A Zahra Sadeghipoor %A Yue M. Lu %A Sabine Susstrunk %XSensors of most digital cameras are made of silicon that is inherently sensitive to both the visible and near-infrared parts of the electromagnetic spectrum. In this paper, we address the problem of color and NIR joint acquisition. We propose a framework for the joint acquisition that uses only a single silicon sensor and a slightly modified version of the Bayer color-filter array that is already mounted in most color cameras. Implementing such a design for an RGB and NIR joint acquisition system requires minor changes to the hardware of commercial color cameras. One of the important differences between this design and the conventional color camera is the post-processing applied to the captured values to reconstruct full resolution images. By using a CFA similar to Bayer, the sensor records a mixture of NIR and one color channel in each pixel. In this case, separating NIR and color channels in different pixels is equivalent to solving an under-determined system of linear equations. To solve this problem, we propose a novel algorithm that uses the tools developed in the field of compressive sensing. Our method results in high-quality RGB and NIR images (the average PSNR of more than 30 dB for the reconstructed images) and shows a promising path towards RGB and NIR cameras.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %C Vancouver, Canada %8 May %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %D 2013 %T Fast non-local filtering by random sampling: It works, especially for large images %A Stanley H. Chan %A Todd Zickler %A Yue M. Lu %XNon-local means (NLM) is a popular denoising scheme. Conceptually simple, the algorithm is computationally intensive for large images. We propose to speed up NLM by using random sampling. Our algorithm picks, uniformly at random, a small number of columns of the weight matrix, and uses these ``representatives'' to compute an approximate result. It also incorporates an extra column-normalization of the sampled columns, a form of symmetrization that often boosts the denoising performance on real images. Using statistical large deviation theory, we analyze the proposed algorithm and provide guarantees on its performance. We show that the probability of having a large approximation error decays exponentially as the image size increases. Thus, for large images, the random estimates generated by the algorithm are tightly concentrated around their limit values, even if the sampling ratio is small. Numerical results confirm our theoretical analysis: the proposed algorithm reduces the run time of NLM, and thanks to the symmetrization step, actually provides some improvement in peak signal-to-noise ratios.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %C Vancouver, Canada %8 May %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %D 2013 %T Detecting random walks hidden in noise: Phase transition on large graphs %A Ameya Agaskar %A Yue M. Lu %XWe consider the problem of distinguishing between two hypotheses: that a sequence of signals on a large graph consists entirely of noise, or that it contains a realization of a random walk buried in the noise. The problem of computing the error exponent of the optimal detector is simple to formulate, but exhibits deep connections to problems known to be difficult, such as computing Lyapunov exponents of products of random matrices and the free entropy density of statistical mechanical systems. We describe these connections, and define an algorithm that efficiently computes the error exponent of the Neyman-Pearson detector. We also derive a closed-form formula, derived from a statistical mechanics-based approximation, for the error exponent on an arbitrary graph of large size. The derivation of this formula is not entirely rigorous, but it closely matches the empirical results in all our experiments. This formula explains a phase transition phenomenon in the error exponent: below a threshold SNR, the error exponent is nearly constant and near zero, indicating poor performance; above the threshold, there is rapid improvement in performance as the SNR increases. The location of the phase transition depends on the entropy rate of the random walk.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) %C Vancouver, Canada %8 May %G eng %0 Journal Article %J Proceedings of the National Academy of Sciences (PNAS) %D 2013 %T Acoustic Echoes Reveal Room Shape %A Ivan Dokmanic %A Reza Parhizkar %A Andreas Walther %A Yue M. Lu %A Martin Vetterli %X Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room’s response. Can you hear the shape of the room? Some people can do it naturally, but can we design computer algorithms that hear rooms? We show how to compute the shape of a convex polyhedral room from its re- sponse to a known sound, recorded by a few microphones. Geo- metric relationships between the arrival times of echoes enable us to “blindfoldedly” estimate the room geometry. This is achieved by exploiting the properties of Euclidean distance matrices. Fur- thermore, we show that under mild conditions, first-order echoes provide a unique description of convex polyhedral rooms. Our algorithm starts from the recorded impulse responses and pro- ceeds by learning the correct assignment of echoes to walls. In contrast to earlier methods, the proposed algorithm reconstructs the full 3D geometry of the room from a single sound emission, and with an arbitrary geometry of the microphone array. As long as the microphones can hear the echoes, we can position them as we want. Besides answering a basic question about the inverse problem of room acoustics, our results find applications in areas such as architectural acoustics, indoor localization, virtual reality, and audio forensics. %B Proceedings of the National Academy of Sciences (PNAS) %V 110 %P 12186-12191 %G eng %U http://www.pnas.org/content/early/2013/06/12/1221464110.full.pdf+html %N 30 %0 Conference Paper %B Proc. 47th Annual Conference on Information Sciences and Systems (CISS) %D 2013 %T Adaptive sensing and inference for single-photon imaging %A Yue M. Lu %XIn recent years, there have been increasing efforts to develop solid-state sensors with single-photon sensitivity, with applications ranging from bio-imaging to 3D computer vision. In this paper, we present adaptive sensing models, theory and algorithms for these single-photon sensors, aiming to improve their dynamic ranges. Mapping different sensor configurations onto a finite set of states, we represent adaptive sensing schemes as finite-state parametric Markov chains. After deriving an asymptotic expression for the Fisher information rate of these Markovian systems, we propose a design criterion for sensing policies based on minimax ratio regret. We also present a suboptimal yet effective sensing policy based on random walks. Numerical experiments demonstrate the strong performance of the proposed scheme, which expands the sensor dynamic ranges of existing nonadaptive approaches by several orders of magnitude.

%B Proc. 47th Annual Conference on Information Sciences and Systems (CISS) %C Baltimore, MD %8 20-22 Mar. %G eng %0 Conference Paper %B Proc. 23rd International Conference on Information Processing in Medical Imaging (IPMI 2013) %D 2013 %T Matched signal detection on graphs: Theory and application to brain network classification %A Chenhui Hu %A Lin Cheng %A Jorge Sepulcre %A Georges El Fakhri %A Yue M. Lu %A Quanzheng Li %X We develop a matched signal detection (MSD) theory for signals with an intrinsic structure described by a weighted graph. Hypothesis tests are formulated under different signal models. In the simplest scenario, we assume that the signal is deterministic with noise in a subspace spanned by a subset of eigenvectors of the graph Laplacian. The conventional matched subspace detection can be easily extended to this case. Furthermore, we study signals with certain level of smoothness. The test turns out to be a weighted energy detector, when the noise variance is negligible. More generally, we presume that the signal follows a prior distribution, which could be learnt from training data. The test statistic is then the difference of signal variations on associated graph structures, if an Ising model is adopted. Effectiveness of the MSD on graph is evaluated both by simulation and real data. We apply it to the network classification problem of Alzheimer’s disease (AD) particularly. The preliminary results demonstrate that our approach is able to exploit the sub-manifold structure of the data, and therefore achieve a better performance than the traditional principle component analysis (PCA). %B Proc. 23rd International Conference on Information Processing in Medical Imaging (IPMI 2013) %C Asilomar, CA %8 29 Jun. - 3 Jul. %G eng %0 Conference Paper %B Proc. International Symposium on Biomedical Imaging (ISBI) %D 2013 %T A graph theoretical regression model for brain connectivity learning of Alzheimer's disease %A Chenhui Hu %A Lin Cheng %A Jorge Sepulcre %A Georges El Fakhri %A Yue M. Lu %A Quanzheng Li %XLearning functional brain connectivity is essential to the understanding of neurodegenerative diseases. In this paper, we introduce a novel graph regression model (GRM) which regards the imaging data as signals defined on a graph and optimizes the fitness between the graph and the data, with a sparsity level regularization. The proposed framework features a nice interpretation in terms of low-pass signals on graphs, and is more generic compared with previous statistical models. Results based on the data illustrates that our approach can obtain a very close reconstruction of the true network. We then apply the GRM to learn the brain connectivity of Alzheimer’s disease (AD). Evaluations performed upon PET imaging data of 30 AD patients demonstrate that the connectivity patterns discovered are easy to interpret and consistent with known pathology.

%B Proc. International Symposium on Biomedical Imaging (ISBI) %C San Francisco, CA %8 7-11 Apr. %G eng %0 Journal Article %J IEEE Transactions on Information Theory %D 2013 %T A Spectral Graph Uncertainty Principle %A Ameya Agaskar %A Yue M. Lu %XThe spectral theory of graphs provides a bridge between classical signal processing and the nascent field of graph signal processing. In this paper, a spectral graph analogy to Heisenberg's celebrated uncertainty principle is developed. Just as the classical result provides a tradeoff between signal localization in time and frequency, this result provides a fundamental tradeoff between a signal's localization on a graph and in its spectral domain. Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral ``spreads'' are given, and a complete characterization of the feasibility region of these two quantities is developed. In particular, the lower boundary of the region, referred to as the uncertainty curve, is shown to be achieved by eigenvectors associated with the smallest eigenvalues of an affine family of matrices. The convexity of the uncertainty curve allows it to be found to within $\varepsilon$ by a fast approximation algorithm requiring $\mathcal{O}(\varepsilon^{-1/2})$ typically sparse eigenvalue evaluations. Closed-form expressions for the uncertainty curves for some special classes of graphs are derived, and an accurate analytical approximation for the expected uncertainty curve of Erdos-Renyi random graphs is developed. These theoretical results are validated by numerical experiments, which also reveal an intriguing connection between diffusion processes on graphs and the uncertainty bounds.

%B IEEE Transactions on Information Theory %V 59 %P 4338-4356 %G eng %N 7 %0 Conference Paper %B Proc. SPIE Conference on Advanced Photon Counting Techniques VI %D 2012 %T Adaptive time-sequential binary sensing for high dynamic range imaging %A Hu, C. %A Lu, Y.M. %XWe present a novel image sensor for high dynamic range imaging. The sensor performs an adaptive one-bit quantization at each pixel, with the pixel output switched from 0 to 1 only if the number of photons reaching that pixel is greater than or equal to a quantization threshold. With an oracle knowledge of the incident light intensity, one can pick an optimal threshold (for that light intensity) and the corresponding Fisher information contained in the output sequence follows closely that of an ideal unquantized sensor over a wide range of intensity values. This observation suggests the potential gains one may achieve by adaptively updating the quantization thresholds. As the main contribution of this work, we propose a time-sequential threshold-updating rule that asymptotically approaches the performance of the oracle scheme. With every threshold mapped to a number of ordered states, the dynamics of the proposed scheme can be modeled as a parametric Markov chain. We show that the frequencies of different thresholds converge to a steady-state distribution that is concentrated around

the optimal choice. Moreover, numerical experiments show that the theoretical performance measures (Fisher information and Cramer-Rao bounds) can be achieved by a maximum likelihood estimator, which is guaranteed to find globally optimal solution due to the concavity of the log-likelihood functions. Compared with conventional image sensors and the strategy that utilizes a constant single-photon threshold considered in previous work, the

proposed scheme attains orders of magnitude improvement in terms of sensor dynamic ranges.

We present a novel regularization framework for demosaicking by viewing images as smooth signals defined on weighted graphs. The restoration problem is formulated as a minimization of variation of these graph-domain signals. As an initial step, we build a weight matrix which measures the similarity between every pair of pixels, from an estimate of the full color image. Subsequently, a two-stage optimization is carried out: first, we assume that the graph Laplacian is signal dependent and solve a non-quadratic problem by gradient descent; then, we pose a variational problem on graphs with a fixed Laplacian, subject to the constraint of consistency given by available samples in each color channel. Performance evaluation shows that our approach can improve existing demosaicking methods both quantitively and visually, by reducing color artifacts.

%B Proc.. IEEE International Conference on Image Processing %C Orlando, FL %8 Sep. %G eng %0 Conference Paper %B Proc. SPIE Conference on Digital Photography VIII %D 2012 %T Optimal spectral sensitivity functions for single sensor color imaging %A Z. Sadeghipoor %A Lu, Y.M. %A S. Süsstrunk %XA cost-effective and convenient approach for color imaging is to use a single sensor and mount a color filter array

(CFA) in front of it, such that at each spatial position the scene information in one color channel is captured. To

estimate the missing colors at each pixel, a demosaicing algorithm is applied to the CFA samples. Besides the

filter arrangement and the demosaicing method, the spectral sensitivity functions of the CFA filters considerably

affect the quality of the demosaiced image. In this paper, we extend the algorithm presented by Lu and Vetterli,

originally proposed for designing the optimum CFA, to compute the optimum spectral sensitivities. The proposed

algorithm solves a constrained optimization problem to find optimum spectral sensitivities and the corresponding

linear demosaicing method. An important constraint for this problem is the smoothness of spectral sensitivities,

which is imposed by modeling these functions as a linear combination of several smooth kernels. Simulation

results verify the effectiveness of the proposed algorithm in finding optimal spectral sensitivity functions, which

outperform measured camera sensitivity functions.

The classical uncertainty principle provides a fundamental tradeoff in the localization of a signal in the time and frequency domains. In this paper we describe a similar tradeoff for signals defined on graphs. We describe the notions of "spread" in the graph and spectral domains, using the eigenvectors of the graph Laplacian as a surrogate Fourier basis. We then describe how to find signals that, among all signals with the same spectral spread, have the smallest graph spread about a given vertex. For every possible spectral spread, the desired signal is the solution to an eigenvalue problem. Since localization in graph and spectral domains is a desirable property of the elements of wavelet frames on graphs, we compare the performance of some existing wavelet transforms to the obtained bound.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Kyoto %8 Mar. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2012 %T Blind estimation and low-rate sampling of sparse MIMO systems with common support %A Y. Xiong %A Lu, Y.M. %XWe present a blind estimation algorithm for multi-input and multi-output (MIMO) systems with sparse common support. Key to the proposed algorithm is a matrix generalization of the classical annihilating filter technique, which allows us to estimate the nonlinear parameters of the channels through an efficient and noniterative procedure. An attractive property of the proposed algorithm is that it only needs the sensor measurements at a narrow frequency band. By exploiting this feature, we can derive efficient sub-Nyquist sampling schemes which significantly reduce the number of samples that need to be retained at each sensor. Numerical simulations verify the accuracy of the proposed estimation algorithm and its robustness in the presence of noise.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Kyoto %8 Mar. %G eng %0 Journal Article %J Foundation and Trends in Signal Processing %D 2012 %T Multidimensional Filter Banks and Multiscale Geometric Representations %A M. N. Do %A Lu, Y.M. %XThanks to the explosive growth of sensing devices and capabilities, multidimensional (MD) signals — such as images, videos, multispectral images, light fields, and biomedical data volumes — have become ubiquitous.

Multidimensional filter banks and the associated constructions provide a unified framework and an efficient computational tool in the formation, representation, and processing of these multidimensional data sets. In this survey we aim to provide a systematic development of the theory and constructions of multidimensional filter banks. We thoroughly review several tools that have been shown to be particularly effective in the design and analysis of multidimensional filter banks, including sampling lattices, multidimensional bases and frames, polyphase representations, Gröbner bases, mapping methods, frequency domain constructions, ladder structures and lifting schemes. We then focus on the construction of filter banks and signal representations that can capture directional and geometric features, which are unique and key properties of many multidimensional signals. Next, we study the connection between iterated multidimensional filter banks in the discrete domain and the associated multiscale signal representations in the continuous domain through a directional multiresolution analysis framework. Finally, we show several examples to demonstrate the power of multidimensional filter banks and geometric signal representations in applications.

We study a new image sensor that is reminiscent of traditional photographic film. Each pixel in the sensor has a binary response, giving only a one-bit quantized measurement of the local light intensity. To analyze its performance, we formulate the oversampled binary sensing scheme as a parameter estimation problem based on quantized Poisson statistics. We show that, with a single-photon quantization threshold and large oversampling factors, the Cramér-Rao lower bound (CRLB) of the estimation variance approaches that of an ideal unquantized sensor, that is, as if there were no quantization in the sensor measurements. Furthermore, the CRLB is shown to be asymptotically achievable by the maximum likelihood estimator (MLE). By showing that the log-likelihood function of our problem is concave, we guarantee the global optimality of iterative algorithms in finding the MLE. Numerical results on both synthetic data and images taken by a prototype sensor verify our theoretical analysis and demonstrate the effectiveness of our image reconstruction algorithm. They also suggest the potential application of the oversampled binary sensing scheme in high dynamic range photography.

%B IEEE Transactions on Image Processing %V 21 %P 1421-1436 %G eng %U http://arxiv.org/abs/1106.0954 %N 4 %0 Conference Paper %B Proc. SPIE Conf. on Wavelets and Sparsity %D 2011 %T An uncertainty principle for functions defined on graphs %A Agaskar, A. %A Lu, Y.M. %XThe classical uncertainty principle provides a fundamental tradeoff in the localization of a function in the time

and frequency domains. In this paper we extend this classical result to functions defined on graphs. We justify

the use of the graph Laplacian’s eigenbasis as a surrogate for the Fourier basis for graphs, and define the notions of "spread" in the graph and spectral domains. We then establish an analogous uncertainty principle relating the two quantities, showing the degree to which a function can be simultaneously localized in the graph and spectral domains.

Joint processing of visible (RGB) and near-infrared (NIR) images has recently found some appealing applications, which make joint capturing a pair of visible and NIR images an important problem. In this paper, we propose a new method to design color filter ar- rays (CFA) and demosaicing matrices for acquiring NIR and visible images using a single sensor. The proposed method modifies the optimum CFA algorithm proposed in [1] by taking advantage of the NIR/visible correlation in the design process. Simulation results show that by applying the proposed method, the quality of demosaiced NIR and visible images is increased by about 1 dB in peak signal-to-noise ratio over the results of the optimum CFA algorithm. It is also shown that better visual quality can be obtained by using the proposed algorithm.

%B Proc. IEEE International Conference on Image Processing %C Brussels %8 Sep. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2011 %T Sparse spectral factorization: Unicity and reconstruction algorithms %A Lu, Y.M. %A M. Vetterli %XSpectral factorization is a classical tool in signal processing and communications. It also plays a critical role in X-ray crystallography, in the context of phase retrieval. In this work, we study the problem of sparse spectral factorization, aiming to recover a one-dimensional sparse signal from its autocorrelation. We present a sufficient condi- tion for the recovery to be unique, and propose an iterative algorithm that can obtain the original signal (up to a sign change, time-shift and time-reversal). Numerical simulations verify the effectiveness of the proposed algorithm.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Prague %G eng %0 Conference Paper %B Proc. Int. Conf. Sampling Theory and applications (SampTA) %D 2011 %T Localizing point sources in diffusion fields from spatiotemporal measurements %A Lu, Y.M. %A P. L. Dragotti %A M. Vetterli %XConsider a diffusion field induced by a finite number of localized and instantaneous sources. In this paper, we study the problem of estimating these sources (including their intensities, spatial locations, and activation time) from the spatiotemporal samples taken by a network of spatially distributed sensors. We propose two estimation algorithms, depending on whether the activation time of the sources is known. For the case of known activation

time, we present an annihilating filter based method to estimate the Euclidean distances between the sources and sensors, which can be subsequently used to localize the sources. For the case of a single source but with unknown activation time, we show that the diffusion field at any spatial location is a scaled and shifted version of a common prototype function, and that this function is the unique solution to a particular differential equation. This observation leads to an efficient algorithm that can estimate the unknown parameters of the source by solving

a system of linear equations. For both algorithms proposed in this work, the minimum number of sensors required is d + 1, where d is the spatial dimension of the field. This requirement is independent of the number of active sources.

We study the spatiotemporal sampling of a diffusion field generated by K point sources, aiming to fully reconstruct the unknown initial field distribution from the sample measurements. The sampling operator in our problem can be described by a matrix derived from the diffusion model. We analyze the important properties of the sampling matrices, leading to precise bounds on the spatial and temporal sampling densities under which perfect field reconstruction is feasible. Moreover, our analysis indicates that it is possible to compensate linearly for insufficient spatial sampling densities by oversampling in time. Numerical simulations on initial field reconstruction under different spatiotemporal sampling densities confirm our theoretical results.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Prague %8 May %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2011 %T Can one hear the shape of a room: The 2-D polygonal case %A I. Dokmanić %A Lu, Y.M. %A M. Vetterli %XWe consider the problem of estimating room geometry from the acoustic room impulse response (RIR). Existing approaches addressing this problem exploit the knowledge of multiple RIRs. In contrast, we are interested in reconstructing the room geometry from a single RIR — a 1–D function of time. We discuss the uniqueness of the mapping between the geometry of a planar polygonal room and a single RIR. In addition to this theoretical analysis, we also propose an algorithm that performs the "blindfolded" room estimation. Furthermore, the derived results are used to construct an algorithm for localization in a known room using only a single RIR. Verification of the theoretical developments with numerical simulations is given before concluding the paper.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Prague %8 May %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2010 %T Learning sparse systems at sub-Nyquist rates: A frequency-domain approach %A M. McCormick %A Lu, Y.M. %A M. Vetterli %XWe propose a novel algorithm for sparse system identification in the frequency domain. Key to our result is the observation that the Fourier transform of the sparse impulse response is a simple sum of complex exponentials, whose parameters can be efficiently determined from only a narrow frequency band. From this perspective, we present a sub-Nyquist sampling scheme, and show that the original continuous-time system can be learned by considering an equivalent low-rate discrete system. The impulse response of that discrete system can then be adaptively obtained by a novel frequency-domain LMS filter, which exploits the parametric structure of the model. Numerical experiments confirm the effectiveness of the proposed scheme for sparse system identification tasks.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Dallas %8 Apr. %G eng %0 Conference Paper %B Proc. Allerton Conference on Communication, Control and Computing. %D 2010 %T Multichannel sampling with unknown gains and offsets: A fast reconstruction algorithm %A Lu, Y.M. %A M. Vetterli %XWe study a multichannel sampling scheme, where different channels observe scaled and shifted versions of a common bandlimited signal. The channel gains and offsets are unknown a priori, and each channel samples at sub-Nyquist rates. This setup appears in many practical signal processing applications, including time-interleaved ADC with timing skews, unsynchronized distributed sampling in sensor networks, and superresolution imaging. In this paper, we propose a new al- gorithm to efficiently estimate the unknown channel gains and offsets. Key to our algorithm is a novel linearization technique, which converts a system of trigonometric polynomial equations of the unknown parameters to an overparameterized linear system. The computation steps of the proposed algorithm boil down to forming a fixed data matrix from the discrete-time Fourier transforms of the observed channel samples and computing the singular value decomposition of that matrix. Numerical simulations verify the effectiveness, efficiency, and robustness of the proposed algorithm in the presence of noise. In the high SNR regime (40 dB and above), the proposed algorithm significantly outperforms a previous method in the literature in terms of estimation accuracy, at the same time being three orders of magnitudes faster.

%B Proc. Allerton Conference on Communication, Control and Computing. %C Monticello, IL %8 Oct. %G eng %0 Conference Paper %B Proc. SPIE Conf. Computational Imaging VIII %D 2010 %T An optimal algorithm for reconstructing images from binary measurements %A F. Yang %A Lu, Y.M. %A L. Sbaiz %A M. Vetterli %B Proc. SPIE Conf. Computational Imaging VIII %C San Jose, CA %8 Jan. %G eng %0 Journal Article %J IEEE Transactions on Signal Processing %D 2010 %T Distributed Sampling of Correlated Signals Linked by Sparse Filtering: Theory and Applications %A A. Hormati %A O. Roy %A Lu, Y.M. %A M. Vetterli %XWe study the distributed sampling and centralized reconstruction of two correlated signals, modeled as the input and output of an unknown sparse filtering operation. This is akin to a Slepian-Wolf setup, but in the sampling rather than the lossless compression case. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in what we call almost sure reconstruction, we allow to have a small set (with measure zero) of unrecoverable signals. We derive achievability bounds on the number of samples needed for both scenarios. Our results show that, only in the almost sure setup can we effectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition to the above theoretical analysis, we propose an efficient and robust distributed sampling and reconstruction algorithm based on annihilating filters. We evaluate the performance of our method in one synthetic scenario, and two practical applications, including the distributed audio sampling in binaural hearing aids and the efficient estimation of room impulse responses. The numerical results confirm the effectiveness and robustness of the proposed algorithm in both synthetic and practical setups.

%B IEEE Transactions on Signal Processing %V 58 %P 1095-1109 %G eng %N 3 %0 Journal Article %J IEEE Transactions on Image Processing %D 2010 %T Demosaicking by Alternating Projections: Theory and Fast One-Step Implementation %A Lu, Y.M. %A M. Karzand %A M. Vetterli %XColor image demosaicking is a key process in the digital imaging pipeline. In this paper, we study a well-known and influential demosaicking algorithm based on alternating projections (AP), proposed by Gunturk, Altunbasak and Mersereau in 2002. Since its publication, the AP algorithm has been widely cited and compared against in a series of more recent papers in the demosaicking literature. Despite good performances, a limitation of the AP algorithm is its high computational complexity. We provide three main contributions in this paper. First, we present a rigorous analysis of the convergence property of the AP demosaicking algorithm, showing that it is a contraction mapping, with a unique fixed point. Second, we show that this fixed point is in fact the solution to a constrained quadratic minimization problem, thus establishing the optimality of the AP algorithm. Finally, using the tool of polyphase representation, we show how to obtain the results of the AP algorithm in a single step, implemented as linear filtering in the polyphase domain. Replacing the original iterative procedure by the proposed one-step solution leads to substantial computational savings, by about an order of magnitude in our experiments.

%B IEEE Transactions on Image Processing %V 19 %P 2085-2098 %G eng %U http://scholar.harvard.edu/yuelu/software/demosaicking-matlab-code-implementing-fast-demosaicking-algorithm-described-following %N 8 %0 Conference Paper %B Proc. Int. Conf. Sampling Theory and applications (SampTA) %D 2009 %T Computable Fourier conditions for alias-free sampling and critical sampling. %A Lu, Y.M. %A M. N. Do %A R. Laugesen %XWe propose a Fourier analytical approach to the problems of alias-free sampling and critical sampling. Central to this approach are two Fourier conditions linking the above sam- pling criteria with the Fourier transform of the indicator function defined on the underlying frequency support. We present several examples to demonstrate the usefulness of the proposed Fourier conditions in the design of critically sampled multidimensional filter banks. In particular, we show that it is impossible to implement any cone-shaped fre- quency partitioning by a nonredundant filter bank, except for the 2-D case.

%B Proc. Int. Conf. Sampling Theory and applications (SampTA) %C Marseille, France %G eng %0 Conference Paper %B Proc. 8th International Conference on Sampling Theory and Applications (SampTA) %D 2009 %T Distributed sensing of signals under a sparse filtering model %A A. Hormati %A O. Roy %A Lu, Y.M. %A M. Vetterli %XWe consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements ob- tained by distributed sensors. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in the case of almost sure recon- struction, we allow to have a small set (with measure zero) of unrecoverable signals. We provide achievability bounds on the number of samples needed for both scenarios. The bounds show that only in the almost sure setup can we ef- fectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition, we propose an efficient and robust distributed sensing and reconstruction algorithm based on annihilating filters.

%B Proc. 8th International Conference on Sampling Theory and Applications (SampTA) %C Marseille, France %G eng %0 Conference Paper %B Proc. IEEE International Conference on Image Processing %D 2009 %T Designing color filter arrays for the joint capture of visible and near-infrared images %A Lu, Y.M. %A C. Fredembach %A M. Vetterli %A S. Süsstrunk %XDigital camera sensors are inherently sensitive to the near- infrared (NIR) part of the light spectrum. In this paper, we propose a general design for color filter arrays that allow the joint capture of visible/NIR images using a single sensor. We pose the CFA design as a novel spatial domain optimization problem, and provide an efficient iterative procedure that finds (locally) optimal solutions. Numerical experiments confirm the effectiveness of the proposed CFA design, which can simultane- ously capture high quality visible and NIR image pairs.

%B Proc. IEEE International Conference on Image Processing %C Cairo, Egypt %G eng %0 Conference Paper %B Proc. 6th International Symposium on Spatial Data Quality %D 2009 %T Assessment of digital surface models for the study of shadowing and radiation over the built environment using wireless sensor network data %A C. Carneiro %A M. Karzand %A F. Golay %A Lu, Y.M. %A M. Vetterli %B Proc. 6th International Symposium on Spatial Data Quality %C Newfoundland %G eng %0 Conference Paper %B Proc. SPIE Electronic Imaging, Digital Photography V %D 2009 %T Optimal color filter array design: Quantitative conditions and an efficient search procedure %A Lu, Y.M. %A M. Vetterli %XMost digital cameras employ a spatial subsampling process, implemented as a color filter array (CFA), to capture color images. The choice of CFA patterns has a great impact on the performance of subsequent reconstruction (demosaicking) algorithms. In this work, we propose a quantitative theory for optimal CFA design. We view the CFA sampling process as an encoding (low-dimensional approximation) operation and, correspondingly, demosaicking as the best decoding (reconstruction) operation. Finding the optimal CFA is thus equivalent to finding the optimal approximation scheme for the original signals with minimum information loss. We present several quantitative conditions for optimal CFA design, and propose an efficient computational procedure to search for the best CFAs that satisfy these conditions. Numerical experiments show that the optimal CFA patterns designed from the proposed procedure can effectively retain the information of the original full-color images. In particular, with the designed CFA patterns, high quality demosaicking can be achieved by using simple and efficient linear filtering operations in the polyphase domain. The visual qualities of the reconstructed images are competitive to those obtained by the state-of-the-art adaptive demosaicking algorithms based on the Bayer pattern.

%B Proc. SPIE Electronic Imaging, Digital Photography V %G eng %0 Journal Article %J IEEE Transactions on Signal Processing %D 2009 %T A Computable Fourier Condition Generating Alias-Free Sampling Lattices %A Lu, Y.M. %A M. N. Do %A R. S. Laugesen %XWe propose a Fourier analytical condition linking alias-free sampling with the Fourier transform of the indicator function defined on the given frequency support. Our discussions center around how to develop practical computation algorithms based on the proposed analytical condition. We address several issues along this line, including the derivation of simple closed-form expressions for the Fourier transforms of the indicator functions defined on arbitrary polygonal and polyhedral domains; a complete and nonredundant enumeration of all quantized sampling lattices via the Hermite normal forms of integer matrices; and a quantitative analysis of the approximation of the original infinite Fourier condition by using finite computations. Combining these results, we propose a computational testing procedure that can efficiently search for the optimal alias-free sampling lattices for a given polygonal or polyhedral shaped frequency domain. Several examples are presented to show the potential of the proposed algorithm in multidimensional filter bank design, as well as in applications involving the design of efficient sampling patterns for multidimensional band-limited signals.

%B IEEE Transactions on Signal Processing %V 57 %P 1768–1782 %8 May %G eng %N 5 %0 Conference Paper %B Proc. 3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) %D 2009 %T Distributed spatio-temporal sampling of diffusion fields from sparse instantaneous sources %A Lu, Y.M. %A M. Vetterli %XWe study the spatio-temporal sampling of a diffusion field driven by K unknown instantaneous source distributions. Exploiting the spatio-temporal correlation offered by the diffusion model, we show that it is possible to compensate for insufficient spatial sampling densities (i.e. sub-Nyquist sampling) by increasing the temporal sampling rate, as long as their product remains roughly a constant. Combining a distributed sparse sampling scheme and an adaptive feedback mechanism, the proposed sampling algorithm can accurately and efficiently estimate the unknown sources and reconstruct the field. The total number of samples to be transmitted through the network is roughly equal to the number of degrees of freedom of the field, plus some additional costs for in-network averaging.

%B Proc. 3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) %C Aruba %8 Dec. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2009 %T Spatial super-resolution of a diffusion field by temporal oversampling in sensor networks %A Lu, Y.M. %A M. Vetterli %XWe study the spatial-temporal sampling of a linear diffusion field, and show that it is possible to compensate for insufficient spatial sampling densities by oversampling in time. Our work is motivated by the following issue often encountered in sensor network sampling, namely increasing the temporal sampling density is often easier and less expensive than increasing the spatial sampling density of the network. For the case of sampling a diffusion field, we show that, to achieve trade-off between spatial and temporal sampling, the spatial arrangement of the sensors must satisfy certain conditions. We provide in this paper the precise relationships between the achievable reduction of spatial sampling density, the required temporal oversampling rate, the spatial arrangement of the sensors, and the bound for the condition numbers of the resulting sampling and reconstruction procedures.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Taiwan %8 Apr. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2009 %T Distributed sensing of signals linked by sparse filtering %A O. Roy %A A. Hormati %A Lu, Y.M. %A M. Vetterli %XWe consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements obtained by distributed sensors. A general formulation of the problem is proposed, under both a universal and an almost sure reconstruction requirement. We then study a specific correlation model which involves a filter that is sparse in the time domain. While this sparsity assumption does not allow reducing the description cost in the universal case, we show that large gains can be achieved in the almost sure scenario by means of a novel distributed scheme based on annihilating filters. The robustness of the proposed method is also investigated.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Taipei %8 Apr. %G eng %0 Conference Paper %B Proc. SPIE Conf. Computational Imaging VI %D 2009 %T Iterative demosaicking accelerated: Theory and fast noniterative implementations %A Lu, Y.M. %A M. Karzand %A M. Vetterli %XColor image demosaicking is a key process in the digital imaging pipeline. In this paper, we present a rigorous treatment of a classical demosaicking algorithm based on alternating projections (AP). Since its publication, the AP algorithm has been widely cited and served as a benchmark in a flurry of papers in the demosaicking literature. Despite its impressive performances, a relative weakness of the AP algorithm is its high computational complexity. In our work, we provide a rigorous analysis of the convergence of the AP algorithm based on the concept of contraction mapping. Furthermore, we propose an efficient noniterative implementation of the AP algorithm in the polyphase domain. Numerical experiments show that the proposed noniterative implementation achieves the same results obtained by the original AP algorithm at convergence, but is about an order of magnitude faster than the latter.

%B Proc. SPIE Conf. Computational Imaging VI %C San Jose, USA %8 Jan. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2008 %T Assessing the challenges of environmental signal processing through the SensorScope project %A G. Barrenetxea %A F. Ingelrest %A Lu, Y.M. %A M. Vetterli %XSensorScope is a collaborative project between network, signal processing, and environmental researchers that aims at providing a cheap and out-of-the-box environmental monitoring system based on a wireless sensor network. It has been successfully used in a number of deployments to gather hundreds of megabytes of environmental data. With data gathering techniques well mastered, the efficient processing of the huge amounts of the acquired information to allow for useful exploitation has become an increasingly important issue. In this paper, we present a number of challenging and relevant signal processing tasks that arise from the SensorScope project. We believe the resolution of these problems will benefit from a better understanding of the underlying physical processes. We show an example to demonstrate how physical correlations between different sensing modalities can help reduce the sampling rate.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Las Vegas, USA %P 5149–5152 %G eng %0 Journal Article %J IEEE Transactions on Signal Processing %D 2008 %T A Mapping-Based Design for Nonsubsampled Hourglass Filter Banks in Arbitrary Dimensions %A Lu, Y.M. %A M. N. Do %XMultidimensional hourglass filter banks decompose the frequency spectrum of input signals into hourglass-shaped directional subbands, each aligned with one of the frequency axes. The directionality of the spectral partitioning makes these filter banks useful in separating the directional information in multi-dimensional signals. Despite the existence of various design techniques proposed for the 2-D case, to our best knowledge, the design of hourglass filter banks in 3-D and higher dimensions with finite impulse response (FIR) filters and perfect reconstruction has not been previously reported. In this paper, we propose a novel mapping-based design for the hourglass filter banks in arbitrary dimensions, featuring perfect reconstruction, FIR filters, efficient implementation using lifting/ladder structures, and a near-tight frame construction. The effectiveness of the proposed mapping-based design depends on the study of a set of conditions on the frequency supports of the mapping kernels. These conditions ensure that we can still get good frequency responses when the component filters used are nonideal. Among all feasible choices, we then propose an optimal specification for the mapping kernels, which leads to the simplest passband shapes and involves the fewest number of frequency variables. Finally, we illustrate the proposed techniques by a design example in 3-D, and an application in video denoising.

%B IEEE Transactions on Signal Processing %V 56 %P 1466-1478 %8 Apr. %G eng %N 4 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2008 %T A Theory for Sampling Signals from a Union of Subspaces %A Lu, Y.M. %A M. N. Do %XOne of the fundamental assumptions in traditional sampling theorems is that the signals to be sampled come from a single vector space (e.g., bandlimited functions). However, in many cases of practical interest the sampled signals actually live in a union of subspaces. Examples include piecewise polynomials, sparse representations, nonuniform splines, signals with unknown spectral support, overlapping echoes with unknown delay and amplitude, and so on. For these signals, traditional sampling schemes based on the single subspace assumption can be either inapplicable or highly inefficient. In this paper, we study a general sampling framework where sampled signals come from a known union of subspaces and the sampling operator is linear. Geometrically, the sampling operator can be viewed as projecting sampled signals into a lower dimensional space, while still preserving all the information. We derive necessary and sufficient conditions for invertible and stable sampling operators in this framework and show that these conditions are applicable in many cases. Furthermore, we find the minimum sampling requirements for several classes of signals, which indicates the power of the framework. The results in this paper can serve as a guideline for designing new algorithms for various applications in signal processing and inverse problems.

%B IEEE Transactions on Signal Processing %V 56 %P 2334–2345 %8 Jun. %G eng %N 6 %0 Journal Article %J IEEE Signal Process. Mag., Special Issue on Compressive Sampling %D 2008 %T Sampling Signals from a Union of Subspaces %A Lu, Y.M. %A M. N. Do %B IEEE Signal Process. Mag., Special Issue on Compressive Sampling %V 25 %8 Mar. %G eng %0 Conference Paper %B Proc. SPIE Conf. on Wavelets Applications in Signal and Image Processing XII %D 2007 %T Sampling signals from a union of shift-invariance subspaces %A Yue M. Lu %A Minh N. Do %B Proc. SPIE Conf. on Wavelets Applications in Signal and Image Processing XII %C San Diego, CA %8 Aug. %G eng %0 Journal Article %J IEEE Transactions on Image Processing %D 2007 %T Multidimensional Directional Filter Banks and Surfacelets %A Lu, Y.M. %A M. N. Do %XIn 1992, Bamberger and Smith proposed the directional filter bank (DFB) for an efficient directional decomposition of 2-D signals. Due to the nonseparable nature of the system, extending the DFB to higher dimensions while still retaining its attractive features is a challenging and previously unsolved problem. We propose a new family of filter banks, named NDFB, that can achieve the directional decomposition of arbitrary ￼ N-dimensional (N >= 2) signals with a simple and efficient tree-structured construction. In 3-D, the ideal passbands of the proposed NDFB are rectangular-based pyramids radiating out from the origin at different orientations and tiling the entire frequency space. The proposed NDFB achieves perfect reconstruction via an iterated filter bank with a redundancy factor of ￼in ￼N-D. The angular resolution of the proposed NDFB can be iteratively refined by invoking more levels of decomposition through a simple expansion rule. By combining the NDFB with a new multiscale pyramid, we propose the surfacelet transform, which can be used to efficiently capture and represent surface-like singularities in multidimensional data.

%B IEEE Transactions on Image Processing %V 16 %P 918-931 %G eng %U http://lu.seas.harvard.edu/software/surfbox-matlab-and-c-toolbox-implementing-surfacelet-transform-described-following-pa %N 4 %0 Conference Paper %B Proc. SPIE Conference on Medical Imaging %D 2007 %T Automatic detection of pelvic lymph nodes using multiple MR sequences %A M. Yan %A Y. Lu %A R. Lu %A M. Requardt %A T. Moeller %A S. Takahashi %A J. Barentsz %B Proc. SPIE Conference on Medical Imaging %C San Diego %8 Feb. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Image Processing %D 2007 %T Finding optimal integral sampling lattices for a given frequency support in multidimensions %A Lu, Y.M. %A M. N. Do %XThe search for alias-free sampling lattices for a given frequency support, in particular those lattices achieving minimum sam- pling densities, is a fundamental issue in various applications of signal and image processing. In this paper, we propose an efficient computational procedure to find all alias-free integral sampling lattices for a given frequency support with minimum sampling density. Central to this algorithm is a novel condition linking the alias-free sampling with the Fourier transform of the indicator function defined on the frequency support. We study the computation of these Fourier transforms based on the diver- gence theorem, and propose a simple closed-form formula for a fairly general class of support regions consisting of arbitrary N -dimensional polytopes, with polygons in 2-D and polyhedra in 3-D as special cases. The proposed algorithm can be useful in a variety of applications involving the design of efficient ac- quisition schemes for multidimensional bandlimited signals.

%B Proc. IEEE International Conference on Image Processing %C San Antonio, USA %G eng %0 Conference Paper %B Proc. SPIE Conf. on Electronic Imaging %D 2007 %T Image interpolation using multiscale geometric representations %A N. Mueller %A Y. Lu %A M. N. Do %XWith the ever increasing computational power of modern day processors, it has become feasible to use more robust and computationally complex algorithms that increase the resolution of images without distorting edges and contours. We present a novel image interpolation algorithm that uses the new contourlet transform to improve the regularity of object boundaries in the generated images. By using a simple wavelet-based linear interpolation scheme as our initial estimate, we use an iterative projection process based on two constraints to drive our solution towards an improved high-resolution image. Our experimental results show that our new algorithm significantly outperforms linear interpolation in subjective quality, and in most cases, in terms of PSNR as well.

%B Proc. SPIE Conf. on Electronic Imaging %C San Jose, USA %G eng %0 Conference Paper %B Fortieth Asilomar Conference on Signals, Systems, and Computers %D 2006 %T Video processing using the 3-dimensional surfacelet transform %A Y. Lu %A M. N. Do %XMotion estimation is a common ingredient in many state-of- the-art video processing algorithms, serving as an effective way to capture the spatial-temporal correlation in video signals. However, the robustness of motion estimation often suffers from problems such as ambiguities of motion trajectory (i.e. the aperture problem) and illumination variances. In this paper, we explore a new framework for video processing based on the recently proposed surfacelet transform. Instead of containing an explicit motion estimation step, the surfacelet transform provides a motion-selective subband decomposition for video signals. We demonstrate the potential of this new technique in a video denoising application.

%B Fortieth Asilomar Conference on Signals, Systems, and Computers %C Pacific Grove, CA %8 Nov. %G eng %0 Conference Paper %B Fortieth Asilomar Conference on Signals, Systems, and Computers %D 2006 %T Multidimensional nonsubsampled hourglass filter banks: Geometry of passband support and filter design %A Y. Lu %A M. N. Do %XRecently, the classical two-dimensional directional filter banks have been extended to higher dimensions. In this paper, we study one of the key components in this new construction, namely the multidimensional nonsubsampled hourglass filter banks. Starting with a rigorous analysis on the geometry of multidimensional hourglass-shaped passband supports, we propose a novel design for these filter banks in arbitrary dimensions, featuring perfect reconstruction and finite impulse response (FIR) filters. We analyze necessary and sufficient conditions for the resulting filters to achieve good frequency responses, and provide an optimal solution that satisfies these conditions using simplest filters. The proposed filter design technique is verified by a design example in 3-D.

%B Fortieth Asilomar Conference on Signals, Systems, and Computers %C Pacific Grove, CA %P 406-410 %8 Nov. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Image Processing %D 2006 %T A new contourlet transform with sharp frequency localization %A Y. Lu %A M. N. Do %XThe contourlet transform was proposed as a directional multiresolution image representation that can efficiently capture and represent singularities along smooth object boundaries in natural images. Its efficient filter bank construction as well as low redundancy make it an attractive computational framework for various image processing applications. However, a major drawback of the original contourlet construction is that its basis images are not localized in the frequency domain. In this paper, we analyze the cause of this problem, and propose a new contourlet construction as a solution. Instead of using the Laplacian pyramid, we employ a new multiscale decomposition defined in the frequency domain. The resulting basis images are sharply localized in the frequency domain and exhibit smoothness along their main ridges in the spatial domain. Numerical experiments on image denoising show that the proposed new contourlet transform can significantly outperform the original transform both in terms of PSNR (by several dB’s) and in visual quality, while with similar computational complexity.

%B Proc. IEEE International Conference on Image Processing %C Atlanta, USA %P 1629-1632 %8 Oct. %G eng %0 Conference Paper %B Proc. of SPIE Conf. on Wavelet Applications in Signal and Image Processing XI %D 2005 %T 3-D directional filter banks and surfacelets %A Y. Lu %A M. N. Do %XIn 1992, Bamberger and Smith proposed the directional filter bank (DFB) for an efficient directional decompo- sition of two-dimensional (2-D) signals. Due to the nonseparable nature of the system, extending the DFB to higher dimensions while still retaining its attractive features is a challenging and previously unsolved problem. This paper proposes a new family of filter banks, named 3DDFB, that can achieve the directional decomposition of 3-D signals with a simple and efficient tree-structured construction. The ideal passbands of the proposed 3DDFB are rectangular-based pyramids radiating out from the origin at different orientations and tiling the whole frequency space. The proposed 3DDFB achieves perfect reconstruction. Moreover, the angular resolution of the proposed 3DDFB can be iteratively refined by invoking more levels of decomposition through a simple expansion rule. We also introduce a 3-D directional multiresolution decomposition, named the surfacelet transform, by combining the proposed 3DDFB with the Laplacian pyramid. The 3DDFB has a redundancy factor of 3 and the surfacelet transform has a redundancy factor up to 24/7.

%B Proc. of SPIE Conf. on Wavelet Applications in Signal and Image Processing XI %C San Diego %P 591-601 %8 Aug. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2005 %T The finer directional wavelet transform %A Y. Lu %A M. N. Do %XDirectional information is an important and unique feature of multidimensional signals. As a result of a separable ex- tension from one-dimensional (1-D) bases, the multidimen- sional wavelet transform has very limited directionality. Furthermore, different directions are mixed in certain wavelet subbands. In this paper, we propose a new transform that fixes this frequency mixing problem by using a simple “add- on” to the wavelet transform. In the 2-D case, it provides one lowpass subband and six directional highpass subbands at each scale. Just like the wavelet transform, the proposed transform is nonredundant, and can be easily extended to higher dimensions. Though nonseparable in essence, the proposed transform has an efficient implementation based on 1-D operations only.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Philadelphia %8 Mar. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2004 %T A geometrical approach to sampling signals with finite rate of innovation %A Y. Lu %A M. N. Do %XMany signals of interest can be characterized by a finite number of parameters per unit of time. Instead of span- ning a single linear space, these signals often lie on a union of spaces. Under this setting, traditional sampling schemes are either inapplicable or very inefficient. We present a framework for sampling these signals based on an injec- tive projection operator, which "flattens" the signals down to a common low dimensional representation space while still preserves all the information. Standard sampling procedures can then be applied on that space. We show the necessary and sufficient conditions for such operators to exist and provide the minimum sampling rate for the representation space, which indicates the efficiency of this framework. These results provide a new perspective on the sampling of signals with finite rate of innovation and can serve as a guideline for designing new algorithms for a class of problems in signal processing and communications.

%B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %C Montreal, Canada %8 May %G eng %0 Conference Paper %B Proc. of SPIE Conference on Wavelet Applications in Signal and Image Processing X %D 2003 %T CRISP-contourlets: A critically-sampled directional multiresultion image representation %A Y. Lu %A M. N. Do %XDirectional multiresolution image representations have lately attracted much attention. A number of new systems, such as the curvelet transform and the more recent contourlet transform, have been proposed. A common issue of these transforms is the redundancy in representation, an undesirable feature for certain applications (e.g. compression). Though some critically sampled transforms have also been proposed in the past, they can only provide limited directionality or limited flexibility in the frequency decomposition. In this paper, we propose a filter bank structure achieving a nonredundant multiresolution and multidirectional expansion of images. It can be seen as a critically sampled version of the original contourlet transform (hence the name CRISP-contourets) in the sense that the corresponding frequency decomposition is similar to that of contourlets, which divides the whole spectrum both angularly and radially. However, instead of performing the multiscale and directional decomposition steps separately as is done in contourlets, the key idea here is to use a combined iterated non- separable filter bank for both steps. Aside from critical sampling, the proposed transform possesses other useful properties including perfect reconstruction, flexible configuration of the number of directions at each scale, and an efficient tree-structured implementation.

%B Proc. of SPIE Conference on Wavelet Applications in Signal and Image Processing X %C San Diego, USA %P 655-665 %8 Aug. %G eng