%0 Conference Paper %D 2024 %T Asymptotics of feature learning in two-layer networks after one gradient-step %A Hugo Cui %A Luca Pesce %A Yatin Dandi %A Florent Krzakala %A Yue M. Lu %A Lenka Zdeborova %A Bruno Loureiro %X In this manuscript we investigate the problem of how two-layer neural networks learn features from data, and improve over the kernel regime, after being trained with a single gradient descent step. Leveraging a connection from (Ba et al., 2022) with a non-linear spiked matrix model and recent progress on Gaussian universality (Dandi et al., 2023), we provide an exact asymptotic description of the generalization error in the high-dimensional limit where the number of samples n, the width p and the input dimension d grow at a proportional rate. We characterize exactly how adapting to the data is crucial for the network to efficiently learn non-linear functions in the direction of the gradient -- where at initialization it can only express linear functions in this regime. To our knowledge, our results provides the first tight description of the impact of feature learning in the generalization of two-layer neural networks in the large learning rate regime η=Θd(d), beyond perturbative finite width corrections of the conjugate and neural tangent kernels. %G eng %U https://arxiv.org/abs/2402.04980 %0 Conference Paper %B Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS) %D 2022 %T Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression %A Lechao Xiao %A Hong Hu %A Theodor Misiakiewicz %A Yue M. Lu %A Pennington, Jeffrey %X As modern machine learning models continue to advance the computational frontier, it has become increasingly important to develop precise estimates for expected performance improvements under different model and data scaling regimes. Currently, theoretical understanding of the learning curves that characterize how the prediction error depends on the number of samples is restricted to either large-sample asymptotics ($m\to\infty$) or, for certain simple data distributions, to the high-dimensional asymptotics in which the number of samples scales linearly with the dimension ($m\propto d$). There is a wide gulf between these two regimes, including all higher-order scaling relations $m\propto d^r$, which are the subject of the present paper. We focus on the problem of kernel ridge regression for dot-product kernels and present precise formulas for the mean of the test error, bias, and variance, for data drawn uniformly from the sphere with isotropic random labels in the $r$th-order asymptotic scaling regime $m\to\infty$ with $m/d^r$ held constant. We observe a peak in the learning curve whenever $m \approx d^r/r!$ for any integer $r$, leading to multiple sample-wise descent and nontrivial behavior at multiple scales.  %B Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS) %G eng %0 Conference Paper %B Mathematical and Scientific Machine Learning %D 2021 %T Construction of optimal spectral methods in phase retrieval %A Antoine Maillard %A Florent Krzakala %A Yue M. Lu %A Lenka Zdeborova %X We consider the phase retrieval problem, in which the observer wishes to recover a n-dimensional real or complex signal X⋆ from the (possibly noisy) observation of |ΦX⋆|, in which Φ is a matrix of size m×n. We consider a \emph{high-dimensional} setting where n,m→∞ with m/n=O(1), and a large class of (possibly correlated) random matrices Φ and observation channels. Spectral methods are a powerful tool to obtain approximate observations of the signal X⋆ which can be then used as initialization for a subsequent algorithm, at a low computational cost. In this paper, we extend and unify previous results and approaches on spectral methods for the phase retrieval problem. More precisely, we combine the linearization of message-passing algorithms and the analysis of the \emph{Bethe Hessian}, a classical tool of statistical physics. Using this toolbox, we show how to derive optimal spectral methods for arbitrary channel noise and right-unitarily invariant matrix Φ, in an automated manner (i.e. with no optimization over any hyperparameter or preprocessing function). %B Mathematical and Scientific Machine Learning %G eng %U https://arxiv.org/abs/2012.04524 %0 Conference Paper %B International Conference on Machine Learning (ICML) %D 2021 %T On the Inherent Regularization Effects of Noise Injection During Training %A Oussama Dhifallah %A Yue M. Lu %X Randomly perturbing networks during the training process is a commonly used approach to improving generalization performance. In this paper, we present a theoretical study of one particular way of random perturbation, which corresponds to injecting artificial noise to the training data. We provide a precise asymptotic characterization of the training and generalization errors of such randomly perturbed learning problems on a random feature model. Our analysis shows that Gaussian noise injection in the training process is equivalent to introducing a weighted ridge regularization, when the number of noise injections tends to infinity. The explicit form of the regularization is also given. Numerical results corroborate our asymptotic predictions, showing that they are accurate even in moderate problem dimensions. Our theoretical predictions are based on a new correlated Gaussian equivalence conjecture that generalizes recent results in the study of random feature models. %B International Conference on Machine Learning (ICML) %G eng %U https://arxiv.org/abs/2102.07379 %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 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. %X

In 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 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 %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 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 %X

We 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 %X

We 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 %X

The 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 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 %X

We 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 Conference Paper %B Allerton Conference on Communications, Control, and Computing %D 2015 %T Phase Retrieval Using Iterative Projections: Dynamics in the Large Systems Limit %A Gen Li %A Yuantao Gu %A Yue M. Lu %X

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 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 %X

Suppose 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 %T

Efficient image reconstruction for gigapixel quantum image sensors

%A S. H. Chan %A Lu, Y.M. %X

Recent 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 %T

Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities

%A Agaskar, A. %A C Wang %A Lu, Y.M. %X

The 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 %T

Finite Dimensional FRI

%A Jon Oñativia %A Yue M. Lu %A Pier Luigi Dragotti %X

Traditional 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 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 %X

We 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 %X

Sensors 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 %X

Non-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 %X

We 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 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 %X

In 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 %X

Learning 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 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. %X

We 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.

%B Proc. SPIE Conference on Advanced Photon Counting Techniques VI %C Baltimore, MD %8 Apr. %G eng %0 Conference Paper %B Proc.. IEEE International Conference on Image Processing %D 2012 %T Graph-Based regularization for color image demosaicking %A Chenhui Hu %A Lin Cheng %A Yue M. Lu %X

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 %X

A 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.

%B Proc. SPIE Conference on Digital Photography VIII %C Burlingame %8 Jan. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2012 %T Uncertainty principles for signals defined on graphs: Bounds and characterizations %A Agaskar, A. %A Lu, Y.M. %X

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. %X

We 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 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. %X

The 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.

%B Proc. SPIE Conf. on Wavelets and Sparsity %C San Diego %8 Aug. %G eng %0 Conference Paper %B Proc. IEEE International Conference on Image Processing %D 2011 %T Correlation-Based joint acquisition and demosaicing of visible and near-infrared images %A Z. Sadeghipoor %A Lu, Y.M. %A S. Susstrunk %X

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 %X

Spectral 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 %X

Consider 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.

%B Proc. Int. Conf. Sampling Theory and applications (SampTA) %C Singapore %G eng %0 Conference Paper %B Proc. IEEE International Conference on Acoustics, Speech and Signal Processing %D 2011 %T Sampling and reconstructing diffusion fields with localized sources %A J. Ranieri %A A. Chebira %A Lu, Y.M. %A M. Vetterli %X

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 %X

We 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 %X

We 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 %X

We 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 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 %X

We 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 %X

We 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 %X

Digital 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 %X

Most 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 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 %X

We 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 %X

We 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 %X

We 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 %X

Color 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 %X

SensorScope 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 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 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 %X

The 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 %X

With 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 %X

Motion 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 %X

Recently, 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 %X

The 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 %X

In 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 %X

Directional 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 %X

Many 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 %X

Directional 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