@article {692521,
	title = {Spectral Universality of Regularized Linear Regression with Nearly Deterministic Sensing Matrices},
	journal = {IEEE Transactions on Information Theory, to appear},
	year = {2024},
	abstract = {It has been observed that the performances of many high-dimensional estimation problems are universal with respect to underlying sensing (or design) matrices. Specifically, matrices with markedly different constructions seem to achieve identical performance if they share the same spectral distribution and have {\textquoteleft}{\textquoteleft}generic{\textquoteright}{\textquoteright} singular vectors. We prove this universality phenomenon for the case of convex regularized least squares (RLS) estimators under a linear regression model with additive Gaussian noise. Our main contributions are two-fold: (1) We introduce a notion of universality classes for sensing matrices, defined through a set of deterministic conditions that fix the spectrum of the sensing matrix and precisely capture the previously heuristic notion of generic singular vectors; (2) We show that for all sensing matrices that lie in the same universality class, the dynamics of the proximal gradient descent algorithm for solving the regression problem, as well as the performance of RLS estimators themselves (under additional strong convexity conditions) are asymptotically identical. In addition to including i.i.d. Gaussian and rotational invariant matrices as special cases, our universality class also contains highly structured, strongly correlated, or even (nearly) deterministic matrices. Examples of the latter include randomly signed versions of incoherent tight frames and randomly subsampled Hadamard transforms. As a consequence of this universality principle, the asymptotic performance of regularized linear regression on many structured matrices constructed with limited randomness can be characterized by using the rotationally invariant ensemble as an equivalent yet mathematically more tractable surrogate.},
	url = {https://arxiv.org/abs/2208.02753},
	author = {Rishabh Dudeja and Subhabrata Sen and Yue M. Lu}
}
@proceedings {722106,
	title = {A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification},
	journal = {IEEE International Symposium on Information Theory (ISIT)},
	year = {2024},
	abstract = {Motivated by the recent application of approximate message passing (AMP) to the analysis of convex optimizations in multi-class classifications [Loureiro, et. al., 2021], we present a convergence analysis of AMP dynamics with non-separable multivariate nonlinearities. As an application, we present a complete (and independent) analysis of the motivated convex optimization problem.},
	url = {https://arxiv.org/abs/2402.08676},
	author = {Burak Cakmak and Yue M. Lu and Manfred Opper}
}
@article {721846,
	title = {Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime},
	year = {2024},
	abstract = {Recent advances in machine learning have been achieved by using overparametrized models trained until near interpolation of the training data. It was shown, e.g., through the double descent phenomenon, that the number of parameters is a poor proxy for the model complexity and generalization capabilities. This leaves open the question of understanding the impact of parametrization on the performance of these models. How does model complexity and generalization depend on the number of parameters\&nbsp;p? How should we choose\&nbsp;p\&nbsp;relative to the sample size\&nbsp;n\&nbsp;to achieve optimal test error?In this paper, we investigate the example of random feature ridge regression (RFRR). This model can be seen either as a finite-rank approximation to kernel ridge regression (KRR), or as a simplified model for neural networks trained in the so-called lazy regime. We consider covariates uniformly distributed on the\&nbsp;d-dimensional sphere and compute sharp asymptotics for the RFRR test error in the high-dimensional polynomial scaling, where\&nbsp;p,n,d{\textrightarrow}$\infty$\&nbsp;while\&nbsp;p/dκ1\&nbsp;and\&nbsp;n/dκ2\&nbsp;stay constant, for all\&nbsp;κ1,κ2∈ℝ\&gt;0. These asymptotics precisely characterize the impact of the number of random features and regularization parameter on the test performance. In particular, RFRR exhibits an intuitive trade-off between approximation and generalization power. For\&nbsp;n=o(p), the sample size\&nbsp;n\&nbsp;is the bottleneck and RFRR achieves the same performance as KRR (which is equivalent to taking\&nbsp;p=$\infty$). On the other hand, if\&nbsp;p=o(n), the number of random features\&nbsp;p\&nbsp;is the limiting factor and RFRR test error matches the approximation error of the random feature model class (akin to taking\&nbsp;n=$\infty$). Finally, a double descent appears at\&nbsp;n=p, a phenomenon that was previously only characterized in the linear scaling\&nbsp;κ1=κ2=1.},
	url = {https://arxiv.org/abs/2403.08160},
	author = {Hong Hu and Yue M. Lu and Theodore Misiakiewicz}
}
@conference {718461,
	title = {Asymptotics of feature learning in two-layer networks after one gradient-step},
	year = {2024},
	abstract = {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\&nbsp;n, the width\&nbsp;p\&nbsp;and the input dimension\&nbsp;d\&nbsp;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\&nbsp;η=Θd(d), beyond perturbative finite width corrections of the conjugate and neural tangent kernels.},
	url = {https://arxiv.org/abs/2402.04980},
	author = {Hugo Cui and Luca Pesce and Yatin Dandi and Florent Krzakala and Yue M. Lu and Lenka Zdeborova and Bruno Loureiro}
}
@article {717301,
	title = {Precise learning curves and higher-order scaling limits for dot-product kernel regression*},
	journal = {Journal of Statistical Mechanics: Theory and Experiment},
	year = {2023},
	url = {https://iopscience.iop.org/article/10.1088/1742-5468/ad01b7},
	author = {Lechao Xiao and Hong Hu and Theodor Misiakiewicz and Yue M. Lu and Pennington, Jeffrey}
}
@article {710746,
	title = {Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime},
	journal = {preprint},
	year = {2023},
	url = {https://arxiv.org/abs/2310.18280},
	author = {Sofiia Dubova and Yue M. Lu and Benjamin McKenna and Horng-Tzer Yau}
}
@article {690114,
	title = {Universality of Approximate Message Passing with Semi-Random Matrices},
	journal = {Annals of Probability, in press},
	volume = {51},
	number = {5},
	year = {2023},
	pages = {1616-1683},
	abstract = {Approximate Message Passing (AMP) is a class of iterative algorithms that have found applications in many problems in high-dimensional statistics and machine learning. In its general form, AMP can be formulated as an iterative procedure driven by a matrix\&nbsp;M. Theoretical analyses of AMP typically assume strong distributional properties on\&nbsp;M\&nbsp;such as\&nbsp;M\&nbsp;has i.i.d. sub-Gaussian entries or is drawn from a rotational invariant ensemble. However, numerical experiments suggest that the behavior of AMP is universal, as long as the eigenvectors of\&nbsp;M\&nbsp;are generic. In this paper, we take the first step in rigorously understanding this universality phenomenon. In particular, we investigate a class of memory-free AMP algorithms (proposed by {\c C}akmak and Opper for mean-field Ising spin glasses), and show that their asymptotic dynamics is universal on a broad class of semi-random matrices. In addition to having the standard rotational invariant ensemble as a special case, the class of semi-random matrices that we define in this work also includes matrices constructed with very limited randomness. One such example is a randomly signed version of the Sine model, introduced by Marinari, Parisi, Potters, and Ritort for spin glasses with fully deterministic couplings.},
	url = {https://arxiv.org/abs/2204.04281},
	author = {Rishabh Dudeja and Yue M. Lu and Subhabrata Sen}
}
@article {690093,
	title = {An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices},
	journal = {Annals of Applied Probability, under minor revision},
	year = {2023},
	abstract = {We consider random matrices whose entries are obtained by applying a (nonlinear) kernel function to the pairwise inner products between \(n\)\&nbsp;independent data vectors drawn uniformly from the unit sphere in \(\mathbb{R}^d\). Our study of this model is motivated by problems in machine learning, statistics, and signal processing, where such inner-product kernel random matrices and their spectral properties play important roles. Under mild conditions on the kernel function, we establish the weak-limit of the empirical spectral distribution of these matrices when \(d, n \to \infty\)\&nbsp;such that\&nbsp;\(n/d^\ell \to \kappa \in (0, \infty)\), for some fixed \(\ell \in \mathbb{N}\)\&nbsp;and \(\kappa \in \mathbb{R}\). This generalizes an earlier result of Cheng and Singer (2013), who studied the same model in the linear scaling regime (with \(\ell = 1\)\&nbsp;and \(n/d \to \kappa\)). The main insight of our work is a general equivalence principle: the spectrum of the random kernel matrix is asymptotically equivalent to that of a simpler matrix model, constructed as the linear combination of a (shifted) Wishart matrix and an independent matrix drawn from the Gaussian orthogonal ensemble. The aspect ratio of the Wishart matrix and the coefficients of the linear combination are determined by \(\ell\)\&nbsp;and by the expansion of the kernel function in the orthogonal Hermite polynomial basis. Consequently, the limiting spectrum of the random kernel matrix can be characterized as the free additive convolution between a Marchenko-Pastur law and a semicircle law.},
	url = {https://arxiv.org/abs/2205.06308},
	author = {Yue M. Lu and HT Yau}
}
@article {665054,
	title = {Universality Laws for High-Dimensional Learning with Random Features},
	journal = {IEEE Transactions on Information Theory, in press},
	year = {2022},
	abstract = {We prove a universality theorem for learning with random features. Our result shows that, in terms of training and generalization errors, the random feature model with a nonlinear activation function is asymptotically equivalent to a surrogate Gaussian model with a matching covariance matrix. This settles a conjecture based on which several recent papers develop their results. Our method for proving the universality builds on the classical Lindeberg approach. Major ingredients of the proof include a leave-one-out analysis for the optimization problem associated with the training process and a central limit theorem, obtained via Stein{\textquoteright}s method, for weakly correlated random variables.},
	url = {https://arxiv.org/abs/2009.07669},
	author = {Hong Hu and Yue M. Lu}
}
@article {633825,
	title = {Asymptotics and Optimal Designs of SLOPE for Sparse Linear Regression},
	journal = {IEEE Transactions on Information Theory},
	volume = {68},
	number = {11},
	year = {2022},
	pages = {7627--7664},
	abstract = {In sparse linear regression, the SLOPE estimator generalizes LASSO by assigning magnitude-dependent regularizations 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 superiority of our optimal design over LASSO and a regularization sequence previously proposed in the literature.},
	url = {https://arxiv.org/abs/1903.11582},
	author = {Hong Hu and Yue M. Lu}
}
@conference {694891,
	title = {Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression},
	booktitle = {Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS)},
	year = {2022},
	abstract = {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.\&nbsp;},
	author = {Lechao Xiao and Hong Hu and Theodor Misiakiewicz and Yue M. Lu and Pennington, Jeffrey}
}
@article {690094,
	title = {Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime},
	journal = {technical report},
	year = {2022},
	abstract = {The generalization performance of kernel ridge regression (KRR) exhibits a multi-phased pattern that crucially depends on the scaling relationship between the sample size\&nbsp;n\&nbsp;and the underlying dimension\&nbsp;d. This phenomenon is due to the fact that KRR sequentially learns functions of increasing complexity as the sample size increases; when\&nbsp;dk-1<<n<<dk, only polynomials with degree less than\&nbsp;k\&nbsp;are learned. In this paper, we present sharp asymptotic characterization of the performance of KRR at the critical transition regions with\&nbsp;n≍dk, for\&nbsp;k∈ℤ+. Our asymptotic characterization provides a precise picture of the whole learning process and clarifies the impact of various parameters (including the choice of the kernel function) on the generalization performance. In particular, we show that the learning curves of KRR can have a delicate "double descent" behavior due to specific bias-variance trade-offs at different polynomial scaling regimes.},
	url = {https://arxiv.org/abs/2205.06798},
	author = {Hong Hu and Yue M. Lu}
}
@article {688200,
	title = {Analysis of Random Sequential Message Passing Algorithms for Approximate Inference},
	journal = {Journal of Statistical Mechanics: Theory and Experiments},
	number = {073401},
	year = {2022},
	abstract = {We analyze the dynamics of a random sequential message passing algorithm for approximate inference with large Gaussian latent variable models in a student-teacher scenario. To model nontrivial dependencies between the latent variables, we assume random covariance matrices drawn from rotation invariant ensembles. Moreover, we consider a model mismatching setting, where the teacher model and the one used by the student may be different. By means of dynamical functional approach, we obtain exact dynamical mean-field equations characterizing the dynamics of the inference algorithm. We also derive a range of model parameters for which the sequential algorithm does not converge. The boundary of this parameter range coincides with the de Almeida Thouless (AT) stability condition of the replica symmetric ansatz for the static probabilistic model.},
	url = {https://arxiv.org/abs/2202.08198},
	author = {B. {\c C}akmak and Yue M. Lu and Manfred Opper}
}
@article {671457,
	title = {Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles},
	journal = {IEEE Transactions on Information Theory},
	volume = {67},
	number = {12},
	year = {2021},
	pages = {8264-8272},
	abstract = {This paper proposes a new algorithm, named Householder Dice (HD), for simulating dynamics on dense random matrix ensembles with translation-invariant properties. Examples include the Gaussian ensemble, the Haar-distributed random orthogonal ensemble, and their complex-valued counterparts. A "direct" approach to the simulation, where one first generates a dense\&nbsp;n{\texttimes}n\&nbsp;matrix from the ensemble, requires at least\&nbsp;O(n2)\&nbsp;resource in space and time. The HD algorithm overcomes this O(n2)\&nbsp;bottleneck by using the principle of deferred decisions: rather than fixing the entire random matrix in advance, it lets the randomness unfold with the dynamics. At the heart of this matrix-free algorithm is an adaptive and recursive construction of (random) Householder reflectors. These orthogonal transformations exploit the group symmetry of the matrix ensembles, while simultaneously maintaining the statistical correlations induced by the dynamics. The memory and computation costs of the HD algorithm are\&nbsp;O(nT)\&nbsp;and\&nbsp;O(nT2), respectively, with\&nbsp;T\&nbsp;being the number of iterations. When\&nbsp;T<<n, which is nearly always the case in practice, the new algorithm leads to significant reductions in runtime and memory footprint. Numerical results demonstrate the promise of the HD algorithm as a new computational tool in the study of high-dimensional random systems.},
	url = {https://arxiv.org/abs/2101.07464},
	author = {Yue M. Lu}
}
@article {665053,
	title = {A Precise Performance Analysis of Learning with Random Features},
	journal = {Technical report},
	year = {2021},
	abstract = {We study the problem of learning an unknown function using random feature models. Our main contribution is an exact asymptotic analysis of such learning problems with Gaussian data. Under mild regularity conditions for the feature matrix, we provide an exact characterization of the asymptotic training and generalization errors, valid in both the under-parameterized and over-parameterized regimes. The analysis presented in this paper holds for general families of feature matrices, activation functions, and convex loss functions. Numerical results validate our theoretical predictions, showing that our asymptotic findings are in excellent agreement with the actual performance of the considered learning problem, even in moderate dimensions. Moreover, they reveal an important role played by the regularization, the loss function and the activation function in the mitigation of the "double descent phenomenon" in learning.},
	url = {https://arxiv.org/abs/2008.11904},
	author = {Oussama Dhifallah and Yue M. Lu}
}
@conference {671456,
	title = {Construction of optimal spectral methods in phase retrieval},
	booktitle = {Mathematical and Scientific Machine Learning},
	year = {2021},
	abstract = {We consider the phase retrieval problem, in which the observer wishes to recover a\&nbsp;n-dimensional real or complex signal\&nbsp;X*\&nbsp;from the (possibly noisy) observation of\&nbsp;|ΦX*|, in which\&nbsp;Φ\&nbsp;is a matrix of size\&nbsp;m{\texttimes}n. We consider a \emph{high-dimensional} setting where\&nbsp;n,m{\textrightarrow}$\infty$\&nbsp;with\&nbsp;m/n=O(1), and a large class of (possibly correlated) random matrices\&nbsp;Φ\&nbsp;and observation channels. Spectral methods are a powerful tool to obtain approximate observations of the signal\&nbsp;X*\&nbsp;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\&nbsp;Φ, in an automated manner (i.e. with no optimization over any hyperparameter or preprocessing function).},
	url = {https://arxiv.org/abs/2012.04524},
	author = {Antoine Maillard and Florent Krzakala and Yue M. Lu and Lenka Zdeborova}
}
@conference {671454,
	title = {On the Inherent Regularization Effects of Noise Injection During Training},
	booktitle = {International Conference on Machine Learning (ICML)},
	year = {2021},
	abstract = {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.},
	url = {https://arxiv.org/abs/2102.07379},
	author = {Oussama Dhifallah and Yue M. Lu}
}
@article {671453,
	title = {Phase Transitions in Transfer Learning for High-Dimensional Perceptrons},
	journal = {Entropy, Special Issue "The Role of Signal Processing and Information Theory in Modern Machine Learning"},
	volume = {23},
	number = {4},
	year = {2021},
	abstract = {Transfer learning seeks to improve the generalization performance of a target task by exploiting the knowledge learned from a related source task. Central questions include deciding what information one should transfer and when transfer can be beneficial. The latter question is related to the so-called negative transfer phenomenon, where the transferred source information actually reduces the generalization performance of the target task. This happens when the two tasks are sufficiently dissimilar. In this paper, we present a theoretical analysis of transfer learning by studying a pair of related perceptron learning tasks. Despite the simplicity of our model, it reproduces several key phenomena observed in practice. Specifically, our asymptotic analysis reveals a phase transition from negative transfer to positive transfer as the similarity of the two tasks moves past a well-defined threshold.},
	url = {https://arxiv.org/abs/2101.01918},
	author = {Oussama Dhifallah and Yue M. Lu}
}
@article {654799,
	title = {The Limiting Poisson Law of Massive MIMO Detection with Box Relaxation},
	journal = {IEEE Journal on Selected Areas in Information Theory},
	volume = {1},
	number = {3},
	year = {2020},
	month = {2020},
	pages = {695-704},
	abstract = {Estimating a binary vector from noisy linear measurements is a prototypical problem for MIMO systems. A popular algorithm, called the box-relaxation decoder, estimates the target signal by solving a least squares problem with convex constraints. This paper shows that the performance of the algorithm, measured by the number of incorrectly-decoded bits, has a limiting Poisson law. This occurs when the sampling ratio and noise variance, two key parameters of the problem, follow certain scalings as the system dimension grows. Moreover, at a well-defined threshold, the probability of perfect recovery is shown to undergo a phase transition that can be characterized by the Gumbel distribution. Numerical simulations corroborate these theoretical predictions, showing that they match the actual performance of the algorithm even in moderate system dimensions.},
	url = {https://arxiv.org/abs/2006.08416},
	author = {Hong Hu and Yue M. Lu}
}
@article {505651,
	title = {Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation},
	journal = {Information and Inference: A Journal of the IMA},
	volume = {9},
	number = {3},
	year = {2020},
	pages = {507-541},
	abstract = {
	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.

},
	url = {https://arxiv.org/abs/1702.06435},
	author = {Yue M. Lu and Gen Li}
}
@conference {654798,
	title = {Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization},
	booktitle = {Conference on Neural Information Processing Systems (NeurIPS)},
	year = {2020},
	month = {2020},
	abstract = {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\&nbsp;α=n/d\&nbsp;is kept finite in the limit of a high dimension\&nbsp;d\&nbsp;and number of samples\&nbsp;n. Our contribution is three-fold: First, we prove a formula for the generalization error achieved by\&nbsp;l2\&nbsp;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\&nbsp;l2\&nbsp;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\&nbsp;α{\textrightarrow}$\infty$\&nbsp;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.},
	url = {https://arxiv.org/abs/2006.06560},
	author = {B. Aubin and Lu, Y.M. and F. Krzakala and L. Zdeborav{\'a}}
}
@conference {654797,
	title = {The role of regularization in classification of high-dimensional noisy Gaussian mixture},
	booktitle = {International Conference on Machine Learning (ICML)},
	year = {2020},
	abstract = {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\&nbsp;n\&nbsp;of samples and their dimension\&nbsp;d\&nbsp;go to infinity while their ratio is fixed to\&nbsp;α=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.},
	url = {https://arxiv.org/abs/2002.11544},
	author = {F. Mignacco and F. Krzakala and Yue M. Lu and L. Zdeborav{\'a}}
}
@article {625850,
	title = {Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval},
	journal = {IEEE Transactions on Signal Processing},
	volume = {67},
	number = {9},
	year = {2019},
	pages = {2347-2356},
	abstract = {We 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.},
	url = {https://arxiv.org/abs/1811.04420},
	author = {Wangyu Luo and Wael Alghamdi and Yue M. Lu}
}
@article {622060,
	title = {Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview},
	journal = {IEEE Transactions on Signal Processing},
	volume = {67},
	number = {20},
	year = {2019},
	pages = {5239-5269},
	abstract = {Substantial 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.},
	url = {https://arxiv.org/abs/1809.09573},
	author = {Yuejie Chi and Yue M. Lu and Yuxin Chen}
}
@article {645554,
	title = {The scaling limit of high-dimensional online independent component analysis},
	journal = {Journal of Statistical Mechanics (Special Issue on Machine Learning)},
	volume = {2019},
	year = {2019},
	abstract = {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 {\textquoteright}decoupled{\textquoteright}, 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.},
	url = {https://iopscience.iop.org/article/10.1088/1742-5468/ab39d6},
	author = {Wang, C. and Lu, Y.M.}
}
@conference {642245,
	title = {A Solvable High-Dimensional Model of GAN},
	booktitle = {Proc. Thirty-third Conference on Neural Information Processing Systems (NeurIPS)},
	year = {2019},
	abstract = {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.},
	url = {https://arxiv.org/abs/1805.08349},
	author = {Chuang Wang and Hong Hu and Yue M. Lu}
}
@conference {637712,
	title = {Generalized Approximate Survey Propagation for High-Dimensional Estimation},
	booktitle = {Proc. International Conference on Machine Learning (ICML)},
	year = {2019},
	abstract = {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.},
	url = {https://arxiv.org/abs/1905.05313},
	author = {L. Saglietti and Lu, Y.M. and C. Lucibello}
}
@conference {637711,
	title = {Asymptotics and optimal designs of SLOPE for sparse linear regression},
	booktitle = {Prof. International Symposium on Information Theory (ISIT)},
	year = {2019},
	abstract = {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.},
	url = {https://arxiv.org/abs/1903.11582},
	author = {H. Hong and Lu, Y.M.}
}
@article {637710,
	title = {Super resolution phase retrieval for sparse signals},
	journal = {IEEE Transactions on Signal Processing},
	volume = {67},
	number = {18},
	year = {2019},
	abstract = {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.\&nbsp;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.},
	url = {https://arxiv.org/abs/1808.01961},
	author = {G. Baechler and M. Krekovi{\'c} and J. Ranieri and A. Chebira and Lu, Y.M. and M. Vetterli}
}
@article {624918,
	title = {MMSE Approximation For Sparse Coding Algorithms Using Stochastic Resonance},
	journal = {IEEE Transactions on Signal Processing},
	volume = {67},
	number = {17},
	year = {2019},
	abstract = {Sparse 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.},
	url = {https://arxiv.org/abs/1806.10171},
	author = {Dror Simon and Jeremias Sulam and Yaniv Romano and Yue M. Lu and Michael Elad}
}
@article {610822,
	title = {Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms},
	journal = {Technical Report},
	year = {2018},
	abstract = {We study algorithms for solving quadratic systems of equations based on optimization methods over polytopes. Our work is inspired by a recently proposed convex formulation of the phase retrieval problem, which estimates the unknown signal by solving a simple linear program over a polytope constructed from the measurements. We present a sharp characterization of the high-dimensional geometry of the aforementioned polytope under Gaussian measurements. This characterization allows us to derive asymptotically exact performance guarantees for PhaseMax, which also reveal a phase transition phenomenon with respect to its sample complexity. Moreover, the geometric insights gained from our analysis lead to a new nonconvex formulation of the phase retrieval problem and an accompanying iterative algorithm, which we call PhaseLamp. We show that this new algorithm has superior recovery performance over the original PhaseMax method. Finally, as yet another variation on the theme of performing phase retrieval via polytope optimization, we propose a weighted version of PhaseLamp and demonstrate, through numerical simulations, that it outperforms several state-of-the-art algorithms under both generic Gaussian measurements as well as more realistic Fourier-type measurements that arise in phase retrieval applications.},
	url = {https://arxiv.org/abs/1805.09555},
	author = {Oussama Dhifallah and Christos Thrampoulidis and Yue M. Lu}
}
@article {609355,
	title = {Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis},
	journal = {IEEE Journal of Selected Topics in Signal Processing},
	volume = {12},
	number = {6},
	year = {2018},
	abstract = {We present a high-dimensional analysis of three popular\&nbsp;algorithms, namely, Oja{\textquoteright}s method, GROUSE and PETRELS, for subspace estimation from streaming and highly incomplete observations. \&nbsp;We show that, with proper time scaling, the time-varying\&nbsp;principal angles between the true subspace and its estimates given by the algorithms\&nbsp;converge weakly to deterministic processes when the ambient dimension\&nbsp;\(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\&nbsp;\(\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{\textquoteright}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.},
	url = {https://arxiv.org/abs/1805.06834},
	author = {Chuang Wang and Yonina C. Eldar and Yue M. Lu}
}
@article {609088,
	title = {A Modern Perspective on Streaming PCA and Subspace Tracking: The Missing Data Case},
	journal = {Proceedings of the IEEE},
	volume = {106},
	number = {8},
	year = {2018},
	month = {Aug 2018},
	pages = {1293-1310},
	abstract = {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 \&nbsp;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.},
	author = {Laura Balzano and Yuejie Chi and Yue M. Lu}
}
@article {473636,
	title = {Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis},
	journal = {IEEE Transactions on Information Theory},
	volume = {64},
	number = {4},
	year = {2018},
	pages = {2639-2647},
	abstract = {Finding 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.},
	url = {https://arxiv.org/abs/1611.07971},
	author = {Yue M. Lu and Jon O{\~n}ativia and Pier Luigi Dragotti}
}
@article {588251,
	title = {Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA},
	journal = {Technical Report},
	year = {2017},
	abstract = {We present a framework for analyzing the exact dynamics of a class of online learning algorithms in the high-dimensional scaling limit. Our results are applied to two concrete examples: online regularized linear regression and principal component analysis. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measures of the target feature vector and its estimates provided by the algorithms 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 can be efficiently obtained. These solutions lead to precise predictions of the performance of the algorithms, as many practical performance metrics are linear functionals of the joint empirical measures. In addition to characterizing the dynamic performance of online learning algorithms, our asymptotic analysis also provides useful insights. In particular, in the high-dimensional limit, and due to exchangeability, the original coupled dynamics associated with the algorithms will be asymptotically {\textquoteleft}{\textquoteleft}decoupled{\textquoteright}{\textquoteright}, with each coordinate independently solving a 1-D effective minimization problem via stochastic gradient descent. Exploiting this insight for nonconvex optimization problems may prove an interesting line of future research.},
	url = {https://arxiv.org/abs/1712.04332},
	author = {Chuang Wang and Jonathan Mattingly and Yue M. Lu}
}
@conference {572726,
	title = {Phase Retrieval via Linear Programming: Fundamental Limits and Algorithmic Improvements},
	booktitle = {55th Annual Allerton Conference on Communication, Control, and Computing},
	year = {2017},
	abstract = {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.},
	url = {https://arxiv.org/abs/1710.05234},
	author = {Oussama Dhifallah and Christos Thrampoulidis and Yue M. Lu}
}
@conference {562356,
	title = {The Scaling Limit of High-Dimensional Online Independent Component Analysis},
	booktitle = {Conference on Neural Information Processing Systems (NIPS)},
	year = {2017},
	note = {Spotlight paper (acceptance rate: 112/3240 = 3.5\%)},
	month = {December},
	abstract = {
	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 {\textquotedblleft}decoupled{\textquotedblright}, 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.\&nbsp;

},
	author = {Chuang Wang and Yue M. Lu}
}
@conference {554691,
	title = {Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis},
	booktitle = {the 7th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)},
	year = {2017},
	note = {
	This paper won the Best Student Paper Award (First Prize) at the 2017 IEEE CAMSAP Workshop.



	The predictions made in this paper via the non-rigorous replica method has since been rigorously established in our latest work.

},
	abstract = {
	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.\&nbsp;

},
	url = {https://arxiv.org/pdf/1708.03355.pdf},
	author = {Oussama Dhifallah and Yue M. Lu}
}
@conference {550646,
	title = {Spectral Initialization for Nonconvex Estimation: High-Dimensional Limit and Phase Transitions},
	booktitle = {IEEE International Symposium on Information Theory (ISIT)},
	year = {2017},
	abstract = {
	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.\&nbsp;

},
	author = {Yue M. Lu and Gen Li}
}
@conference {518216,
	title = {Subspace Estimation from Incomplete Observations: A Precise High-Dimensional Analysis},
	booktitle = {Signal Processing with Adaptive Structured Representatives (SPARS) Workshop},
	year = {2017},
	month = {5 - 8 June},
	abstract = {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\&nbsp;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.\&nbsp;},
	author = {Chuang Wang and Yonina Eldar and Yue M. Lu}
}
@article {428401,
	title = {A Tale of Two Bases: Local-Nonlocal Regularization on Image Patches with Convolution Framelets},
	journal = {SIAM Journal on Imaging Sciences},
	volume = {10},
	number = {2},
	year = {2017},
	month = {2017},
	pages = {711-750},
	abstract = {
	We propose an image representation scheme combining the local and nonlocal\&nbsp;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.\&nbsp;

},
	author = {Ruijie Yin and Tingran Gao and Yue M. Lu and Ingrid Daubechies}
}
@article {360276,
	title = {Understanding Symmetric Smoothing Filters: A Gaussian Mixture Model Perspective},
	journal = {IEEE Transactions on Image Processing},
	volume = {26},
	number = {11},
	year = {2017},
	month = {Nov 2017},
	pages = {5107-5121},
	abstract = {
	Many 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.

},
	url = {http://arxiv.org/abs/1601.00088},
	author = {Stanley H. Chan and Todd Zickler and Yue M. Lu}
}
@conference {451501,
	title = {Online Learning for Sparse PCA in High Dimensions: Exact Dynamics and Phase Transitions},
	booktitle = {IEEE Information Theory Workshop (ITW)},
	year = {2016},
	month = {September},
	abstract = {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{\textquoteright}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.},
	author = {Chuang Wang and Yue M. Lu}
}
@conference {416416,
	title = {ProSparse denoise: Prony{\textquoteright}s based sparsity pattern recovery in the presence of noise},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
	year = {2016},
	month = {March},
	author = {J. Onativia and P. L. Dragotti and Yue M. Lu}
}
@article {415726,
	title = {Kaczmarz Method for Solving Quadratic Equations},
	journal = {IEEE Signal Processing Letters},
	volume = {23},
	number = {9},
	year = {2016},
	month = {2016},
	pages = {1183-1187},
	abstract = {Estimating 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.},
	author = {Yuejie Chi and Yue M. Lu}
}
@article {360281,
	title = {Decomposition space-variant blur in image deconvolution},
	journal = {IEEE Signal Processing Letters},
	volume = {23},
	number = {3},
	year = {2016},
	month = {Mar 2016},
	pages = {346-350},
	abstract = {


Standard convolution as a model of radiometric degradation is in majority of cases inaccurate as the blur varies in space and we are thus required to work with a computationally demanding space-variant model. Space-variant degradation can be approximately decomposed to a set of standard convolutions. We explain in detail the properties of the space-variant degrada- tion operator and show two possible decomposition models and two approximation approaches. Our target application is space- variant image deconvolution, on which we illustrate theoretical differences between these models. We propose a computationally efficient restoration algorithm that belongs to a category of alternating direction methods of multipliers, which consists of four update steps with closed-form solutions. Depending on the used decomposition, two variations of the algorithm exist with distinct properties. We test the effectiveness of the decomposition models under different levels of approximation on synthetic and real examples, and conclude the letter by drawing several practical observations.\&nbsp;


},
	author = {Filip Sroubek and Jan Kamenicky and Yue M. Lu}
}
@article {343426,
	title = {Dynamics of Individual Perceptual Decisions},
	journal = {Journal of Neurophysiology},
	volume = {115},
	number = {1},
	year = {2016},
	month = {2016},
	abstract = {Perceptual 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).},
	url = {http://jn.physiology.org/content/early/2015/10/09/jn.00225.2015},
	author = {Daniel M. Merfeld and Torin K. Clark and Yue M. Lu and Faisal Karmali}
}
@article {343431,
	title = {Matched Signal Detection on Graphs: Theory and Application to Brain Imaging Data Classification},
	journal = {NeuroImage},
	volume = {125},
	year = {2016},
	month = {2015},
	pages = {587-600},
	abstract = {


Motivated by recent progresses in signal processing on graphs, we have developed a matched signal detection (MSD) theory for signals with intrinsic structures described by weighted graphs. First, we regard graph Laplacian eigenvalues as frequencies of graph-signals and assume that the signal is in a subspace spanned by the first few graph Laplacian eigenvectors associated with lower eigenvalues. The conventional matched subspace detector can be applied to this case. Furthermore, we study signals that may not merely live in a subspace. Namely, we consider signals with bounded variation on graphs and more general signals that are randomly drawn from a prior distribution. For bounded variation signals, the test is a weighted energy detector. For the random signals, the test statistic is the difference of signal variations on associated graphs, if a degenerate Gaussian distribution specified by the graph Laplacian is adopted. We evaluate the effectiveness of the MSD on graphs both on simulated and real data sets. Specifically, we apply MSD to the brain imaging data classification problem of Alzheimer{\textquoteright}s disease (AD) based on two independent data sets: 1) positron emission tomography data with Pittsburgh compound-B tracer of 30 AD and 40 normal control (NC) subjects, 2) resting-state functional magnetic resonance imaging (R-fMRI) data of 30 early mild cognitive impairment and 20 NC subjects. Our results demonstrate that the MSD approach is able to outperform the traditional methods and help detect AD at an early stage, probably due to the success of exploiting the manifold structure of the data.\&nbsp;


},
	author = {Chenhui Hu and Jorge Sepulcre and Keith A. Johnson and George E. Fakhri and Yue M. Lu and Quangzheng Li}
}
@article {252486,
	title = {A Distributed Gauss-Newton Method for Power System State Estimation},
	journal = {IEEE Transactions on Power Systems},
	volume = {31},
	number = {5},
	year = {2016},
	month = {2016},
	pages = {3804-3815},
	abstract = {We 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.},
	author = {Ariana Minot and Yue M. Lu and N. Li}
}
@article {237816,
	title = {Sampling Sparse Signals on the Sphere: Algorithms and Applications},
	journal = {IEEE Transactions on Signal Processing},
	volume = {64},
	number = {1},
	year = {2016},
	month = {2015},
	pages = {189-202},
	abstract = {We propose a sampling scheme that can perfectly reconstruct a collection ofspikes on the sphere from samples of their lowpass-filtered observations.Central to our algorithm is a generalization of the annihilating filtermethod, a tool widely used in array signal processing and finite-rate-of-innovation(FRI) sampling. The proposed algorithm can reconstruct $K$ spikesfrom $(K+\sqrt{K})^2$ spatial samples---a sampling requirement thatimproves over known sparse sampling schemes on the sphere by a factor of upto four.We showcase the versatility of the proposed algorithm by applying it tothree different problems: 1) sampling diffusion processes induced bylocalized sources on the sphere, 2) shot-noise removal, and 3) sound sourcelocalization (SSL) by a spherical microphone array. In particular, we showhow SSL can be reformulated as a spherical sparse sampling problem.},
	url = {http://arxiv.org/abs/1502.07577},
	author = {Ivan Dokmanic and Yue M. Lu}
}
@conference {416411,
	title = {Phase Retrieval Using Iterative Projections: Dynamics in the Large Systems Limit},
	booktitle = {Allerton Conference on Communications, Control, and Computing},
	year = {2015},
	month = {October},
	abstract = {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.},
	author = {Gen Li and Yuantao Gu and Yue M. Lu}
}
@conference {416446,
	title = {Understanding symmetric smoothing filters via Gaussian mixtures},
	booktitle = {IEEE International Conference on Image Processing},
	year = {2015},
	month = {September},
	author = {Stanley H. Chan and Todd Zickler and Yue M. Lu}
}
@conference {254936,
	title = {Sparsity according to Prony, Average Performance Analysis},
	booktitle = {Signal Processing with Adaptive Sparse Structured Representations (SPARS) Workshop},
	year = {2015},
	month = {Jul.},
	address = {Cambridge, England},
	author = {Jon Onativia and Pier Luigi Dragotti and Yue M. Lu}
}
@article {254926,
	title = {A Spectral Graph Regression Model for Learning Brain Connectivity of Alzheimer{\textquoteright}s Disease},
	journal = {PLOS ONE},
	volume = {10},
	number = {5},
	year = {2015},
	month = {2015},
	abstract = {Understanding network features of brain pathology is essential to reveal underpinnings\&nbsp;of neurodegenerative diseases. In this paper, we introduce a novel graph regression\&nbsp;model (GRM) for learning structural brain connectivity of Alzheimer{\textquoteright}s disease (AD)\&nbsp;measured by amyloid-β\&nbsp; deposits. The proposed GRM regards 11 C-labeled Pittsburgh\&nbsp;Compound-B (PiB) positron emission tomography (PET) imaging data as smooth\&nbsp;signals defined on an unknown graph. This graph is then estimated through an\&nbsp;optimization framework, which fits the graph to the data with an adjustable level of\&nbsp;uniformity of the connection weights. Under the assumed data model, results based on\&nbsp;simulated data illustrate that our approach can accurately reconstruct the underlying\&nbsp;network, often with better reconstruction than those obtained by both sample\&nbsp;correlation and l1 -regularized partial correlation estimation. Evaluations performed\&nbsp;upon PiB-PET imaging data of 30 AD and 40 elderly normal control (NC) subjects\&nbsp;demonstrate that the connectivity patterns revealed by the GRM are easy to interpret\&nbsp;and consistent with known pathology. Moreover, the hubs of the reconstructed\&nbsp;networks match the cortical hubs given by functional MRI. The discriminative network\&nbsp;features including both global connectivity measurements and degree statistics of\&nbsp;specific nodes discovered from the AD and NC amyloid-beta networks provide new\&nbsp;potential biomarkers for preclinical and clinical AD.},
	url = {http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0128136},
	author = {Chenhui Hu and Lin Cheng and Jorge Sepulcre and Keith A. Johnson and Georges E. Fakhri and Yue M. Lu and Quanzheng Li}
}
@article {253216,
	title = {Optimal Detection of Random Walks on Graphs: Performance Analysis via Statistical Physics},
	journal = {Technical Report},
	year = {2015},
	abstract = {
	We study the problem of detecting a random walk on a graph from a sequence of noisy measurements at every node.\&nbsp;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\&nbsp;over time.\&nbsp;We want to exploit knowledge of the graph structure and random walk parameters (specified by a Markov chain\&nbsp;transition matrix) to detect a possibly very weak signal.\&nbsp;The optimal detector is easily derived, and we focus on the harder problem of characterizing its performance through the\&nbsp;(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\&nbsp;techniques from that field to develop a lower bound. Our fully\&nbsp;rigorous analysis uses large deviations theory to show that the lower bound exhibits a phase transition: strong\&nbsp;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.

},
	url = {http://arxiv.org/abs/1504.06924},
	author = {Agaskar, A. and Lu, Y.M.}
}
@conference {235161,
	title = {Optimal hypothesis testing with combinatorial structure: Detecting random walks on graphs},
	booktitle = {Proc. of Asilomar Conference on Signals, Systems and Computers},
	year = {2014},
	month = {Nov.},
	address = {Pacific Grove, CA},
	abstract = {Suppose we have a time series of observations for each node\&nbsp;in a network, and we wish to detect the presence of a particle\&nbsp;undergoing a random walk on the network. If there is no such\&nbsp;particle, then we observe only zero-mean Gaussian noise. If\&nbsp;present, however, the location of the particle has an elevated\&nbsp;mean. How well can we detect the particle at low signal-to-noise\&nbsp;ratios? This is a special case of the problem of detecting\&nbsp;hidden Markov processes (HMPs).
The performance metric we analyze is the error exponent of\&nbsp;the optimal detector, which measures the exponential rate of decay\&nbsp;in the miss probability if the false alarm probability is held\&nbsp;fixed as the observation time increases. This problem exhibits\&nbsp;deep connections to a problem in statistical physics: computing\&nbsp;the free energy density of a spin glass.\&nbsp;
We develop a generalized version of the random energy\&nbsp;model (REM) spin glass, whose free energy density provides\&nbsp;a lower bound for our error exponent, and compute the bound\&nbsp;using large deviations techniques. The bound closely matches\&nbsp;empirical results in numerical experiments, and suggests a\&nbsp;phase transition phenomenon: below a threshold SNR, the error\&nbsp;exponent is nearly constant and near zero, indicating poor\&nbsp;performance; above the threshold, there is rapid improvement\&nbsp;in performance as the SNR increases. The location of the phase\&nbsp;transition depends on the entropy rate of the Markov process.},
	author = {Ameya Agaskar and Yue M. Lu}
}
@conference {208961,
	title = {Efficient image reconstruction for gigapixel quantum image sensors},
	booktitle = {IEEE Global Conference on Signal and Information Processing (GlobalSIP)},
	year = {2014},
	month = {Dec.},
	address = {Atlanta, GA},
	abstract = {Recent advances in materials, devices and fabrication technologies\&nbsp;have motivated a strong momentum in developing solid-state sensors\&nbsp;that can detect individual photons in space and time. It has been envisioned\&nbsp;that such sensors can eventually achieve very high spatial\&nbsp;resolutions (e.g., 10^9 pixels/chip) as well as high frame rates (e.g.,\&nbsp;10^6 frames/sec). In this paper, we present an efficient algorithm to\&nbsp;reconstruct images from the massive binary bit-streams generated by\&nbsp;these sensors. Based on the concept of alternating direction method\&nbsp;of multipliers (ADMM), we transform the computationally intensive\&nbsp;optimization problem into a sequence of subproblems, each of which\&nbsp;has efficient implementations in the form of polyphase-domain filtering\&nbsp;or pixel-wise nonlinear mappings. Moreover, we reformulate\&nbsp;the original maximum likelihood estimation as maximum a posterior\&nbsp;estimation by introducing a total variation prior. Numerical results\&nbsp;demonstrate the strong performance of the proposed method,\&nbsp;which achieves several dB{\textquoteright}s of improvement in PSNR and requires a\&nbsp;shorter runtime as compared to standard gradient-based approaches.},
	author = {S. H. Chan and Lu, Y.M.}
}
@conference {208966,
	title = {Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities},
	booktitle = {IEEE Global Conference on Signal and Information Processing (GlobalSIP)},
	year = {2014},
	note = {(This paper received the Best Student Paper Award of GlobalSIP)},
	month = {Dec.},
	address = {Atlanta, GA},
	abstract = {The Kaczmarz method, or the algebraic reconstruction technique\&nbsp;(ART), is a popular method for solving large-scale overdetermined\&nbsp;systems of equations. Recently, Strohmer et al. proposed the randomized\&nbsp;Kaczmarz algorithm, an improvement that guarantees exponential\&nbsp;convergence to the solution. This has spurred much interest\&nbsp;in the algorithm and its extensions. We provide in this paper an exact\&nbsp;formula for the mean squared error (MSE) in the value reconstructed\&nbsp;by the algorithm. We also compute the exponential decay rate of\&nbsp;the MSE, which we call the {\textquotedblleft}annealed{\textquotedblright} error exponent. We show\&nbsp;that the typical performance of the algorithm is far better than the\&nbsp;average performance. We define the {\textquotedblleft}quenched{\textquotedblright} error exponent to\&nbsp;characterize the typical performance. This is far harder to compute\&nbsp;than the annealed error exponent, but we provide an approximation\&nbsp;that matches empirical results. We also explore optimizing the\&nbsp;algorithm{\textquoteright}s row-selection probabilities to speed up the algorithm{\textquoteright}s\&nbsp;convergence.},
	author = {Agaskar, A. and C Wang and Lu, Y.M.}
}
@conference {170916,
	title = {Finite Dimensional FRI},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
	year = {2014},
	month = {May},
	address = {Florence},
	abstract = {Traditional Finite Rate of Innovation (FRI) theory has considered\&nbsp;the problem of sampling continuous-time signals. This framework can be naturally extended to the case where the\&nbsp;input is a discrete-time signal. Here we present a novel approach\&nbsp;which uses both the traditional FRI sampling scheme,\&nbsp;based on the annihilating filter method, and the fact that in\&nbsp;this new setup the null space of the problem to be solved is\&nbsp;finite dimensional.

In the noiseless scenario, we show that this new approach\&nbsp;is able to perfectly recover the original signal at the critical\&nbsp;sampling rate. We also present simulation results in the noisy\&nbsp;scenario where this new approach improves performances in\&nbsp;terms of the mean squared error (MSE) of the reconstructed\&nbsp;signal when compared to the canonical FRI algorithms and\&nbsp;compressed sensing (CS).},
	author = {Jon O{\~n}ativia and Yue M. Lu and Pier Luigi Dragotti}
}
@article {140861,
	title = {Monte Carlo Non-Local Means: Random Sampling for Large-Scale Image Filtering},
	journal = {IEEE Transactions on Image Processing},
	volume = {23},
	number = {8},
	year = {2014},
	pages = {3711-3725},
	abstract = {We 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.},
	author = {Stanley H. Chan and Todd Zickler and Yue M. Lu}
}
@article {126551,
	title = {On Sparse Representation in Fourier and Local Bases},
	journal = {IEEE Transactions on Information Theory},
	volume = {60},
	number = {12},
	year = {2014},
	month = {2014},
	pages = {7888-7899},
	abstract = {We 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\&lt;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\&lt;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\&lt;\sqrt{2} /\mu(\mD)$. Consequently, when $K\&lt;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.},
	author = {Pier Luigi Dragotti and Yue M. Lu}
}
@article {73676,
	title = {Sensor Placement for the Analysis of Seismic Surface Waves: Source of Error, Design Criterion, and Array Design Algorithms},
	journal = {Geophys. J. Int.},
	volume = {197},
	number = {3},
	year = {2014},
	pages = {1566-1581},
	abstract = {Seismic 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.},
	url = {http://gji.oxfordjournals.org/content/197/3/1566.full.pdf+html},
	author = {Stefano Maran{\`o} and Donat F{\"a}h and Yue M. Lu}
}
@conference {137101,
	title = {A Framework for Adaptive Parameter Estimation with Finite Memory},
	booktitle = {Proc. IEEE Global Conference on Signal and Information Processing},
	year = {2013},
	month = {Dec. 3 - 5},
	address = {Austin, TX},
	abstract = {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.},
	author = {Yue M. Lu}
}
@conference {137096,
	title = {ALARM: A Logistic Auto-Regressive Model for binary processes on networks},
	booktitle = {Proc. IEEE Global Conference on Signal and Information Processing},
	year = {2013},
	month = {Dec. 3 - 5},
	address = {Austin, TX},
	abstract = {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{\textquoteright} 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.},
	author = {Ameya Agaskar and Yue M. Lu}
}
@conference {70801,
	title = {A novel compressive sensing approach to simultaneously acquire color and near-infrared images on a single sensor},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
	year = {2013},
	month = {May},
	address = {Vancouver, Canada},
	abstract = {Sensors of most digital cameras are made of silicon that is inherently\&nbsp;sensitive to both the visible and near-infrared parts of the electromagnetic\&nbsp;spectrum. In this paper, we address the problem of color\&nbsp;and NIR joint acquisition. We propose a framework for the joint\&nbsp;acquisition that uses only a single silicon sensor and a slightly modified\&nbsp;version of the Bayer color-filter array that is already mounted\&nbsp;in most color cameras. Implementing such a design for an RGB and\&nbsp;NIR joint acquisition system requires minor changes to the hardware\&nbsp;of commercial color cameras.\&nbsp;One of the important differences between this design and the\&nbsp;conventional color camera is the post-processing applied to the captured\&nbsp;values to reconstruct full resolution images. By using a CFA\&nbsp;similar to Bayer, the sensor records a mixture of NIR and one color\&nbsp;channel in each pixel. In this case, separating NIR and color channels\&nbsp;in different pixels is equivalent to solving an under-determined\&nbsp;system of linear equations. To solve this problem, we propose a\&nbsp;novel algorithm that uses the tools developed in the field of compressive\&nbsp;sensing. Our method results in high-quality RGB and NIR\&nbsp;images (the average PSNR of more than 30 dB for the reconstructed\&nbsp;images) and shows a promising path towards RGB and NIR cameras.\&nbsp;},
	author = {Zahra Sadeghipoor and Yue M. Lu and Sabine Susstrunk}
}
@conference {70796,
	title = {Fast non-local filtering by random sampling: It works, especially for large images},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
	year = {2013},
	month = {May},
	address = {Vancouver, Canada},
	abstract = {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 {\textquoteleft}{\textquoteleft}representatives{\textquoteright}{\textquoteright} 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.},
	author = {Stanley H. Chan and Todd Zickler and Yue M. Lu}
}
@conference {70791,
	title = {Detecting random walks hidden in noise: Phase transition on large graphs},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
	year = {2013},
	month = {May},
	address = {Vancouver, Canada},
	abstract = {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\&nbsp;in the noise. The problem of computing the error exponent of the optimal detector\&nbsp;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.\&nbsp;We describe these connections, and define an\&nbsp;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\&nbsp;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\&nbsp;constant and near zero, indicating poor performance; above the threshold, there is rapid improvement\&nbsp;in performance as the SNR increases. The location of the phase transition depends on the entropy rate of the random walk.},
	author = {Ameya Agaskar and Yue M. Lu}
}
@article {69951,
	title = {Acoustic Echoes Reveal Room Shape},
	journal = {Proceedings of the National Academy of Sciences (PNAS)},
	volume = {110},
	number = {30},
	year = {2013},
	pages = {12186-12191},
	abstract = {Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room{\textquoteright}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 {\textquotedblleft}blindfoldedly{\textquotedblright} 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.},
	url = {http://www.pnas.org/content/early/2013/06/12/1221464110.full.pdf+html},
	author = {Ivan Dokmanic and Reza Parhizkar and Andreas Walther and Yue M. Lu and Martin Vetterli}
}
@conference {69941,
	title = {Adaptive sensing and inference for single-photon imaging},
	booktitle = {Proc. 47th Annual Conference on Information Sciences and Systems (CISS)},
	year = {2013},
	month = {20-22 Mar.},
	address = {Baltimore, MD},
	abstract = {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.},
	author = {Yue M. Lu}
}
@conference {64916,
	title = {Matched signal detection on graphs: Theory and application to brain network classification},
	booktitle = {Proc. 23rd International Conference on Information Processing in Medical Imaging (IPMI 2013)},
	year = {2013},
	month = {29 Jun. - 3 Jul.},
	address = {Asilomar, CA},
	abstract = {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{\textquoteright}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).},
	author = {Chenhui Hu and Lin Cheng and Jorge Sepulcre and Georges El Fakhri and Yue M. Lu and Quanzheng Li}
}
@conference {55846,
	title = {A graph theoretical regression model for brain connectivity learning of Alzheimer{\textquoteright}s disease},
	booktitle = {Proc. International Symposium on Biomedical Imaging (ISBI)},
	year = {2013},
	month = {7-11 Apr.},
	address = {San Francisco, CA},
	abstract = {Learning functional brain connectivity is essential to the\&nbsp;understanding of neurodegenerative diseases. In this paper,\&nbsp;we introduce a novel graph regression model (GRM) which\&nbsp;regards the imaging data as signals defined on a graph\&nbsp;and optimizes the fitness between the graph and the data,\&nbsp;with a sparsity level regularization. The proposed framework\&nbsp;features a nice interpretation in terms of low-pass\&nbsp;signals on graphs, and is more generic compared with\&nbsp;previous statistical models. Results based on the data illustrates that our approach can obtain a very close\&nbsp;reconstruction of the true network. We then apply the GRM\&nbsp;to learn the brain connectivity of Alzheimer{\textquoteright}s disease (AD).\&nbsp;Evaluations performed upon PET imaging data of 30 AD patients\&nbsp;demonstrate that the connectivity patterns discovered\&nbsp;are easy to interpret and consistent with known pathology.},
	author = {Chenhui Hu and Lin Cheng and Jorge Sepulcre and Georges El Fakhri and Yue M. Lu and Quanzheng Li}
}
@article {33212,
	title = {A Spectral Graph Uncertainty Principle},
	journal = {IEEE Transactions on Information Theory},
	volume = {59},
	number = {7},
	year = {2013},
	pages = {4338-4356},
	abstract = {The 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{\textquoteright}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{\textquoteright}s localization on a graph and in its spectral domain.\&nbsp;Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral {\textquoteleft}{\textquoteleft}spreads{\textquoteright}{\textquoteright} are given,\&nbsp;and a complete characterization of the feasibility region of these two quantities is developed.\&nbsp;In particular, the lower boundary of the region, referred to as the uncertainty curve,\&nbsp;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.\&nbsp;Closed-form expressions for the uncertainty curves for some special classes of graphs are derived,\&nbsp;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.},
	author = {Ameya Agaskar and Yue M. Lu}
}
@conference {36964,
	title = {Adaptive time-sequential binary sensing for high dynamic range imaging},
	booktitle = {Proc. SPIE Conference on Advanced Photon Counting Techniques VI},
	year = {2012},
	month = {Apr.},
	address = {Baltimore, MD},
	abstract = {We present a novel image sensor for high dynamic range imaging. The sensor performs an adaptive one-bit\&nbsp;quantization at each pixel, with the pixel output switched from 0 to 1 only if the number of photons reaching\&nbsp;that pixel is greater than or equal to a quantization threshold. With an oracle knowledge of the incident light\&nbsp;intensity, one can pick an optimal threshold (for that light intensity) and the corresponding Fisher information\&nbsp;contained in the output sequence follows closely that of an ideal unquantized sensor over a wide range of intensity\&nbsp;values. This observation suggests the potential gains one may achieve by adaptively updating the quantization\&nbsp;thresholds. As the main contribution of this work, we propose a time-sequential threshold-updating rule that\&nbsp;asymptotically approaches the performance of the oracle scheme. With every threshold mapped to a number of\&nbsp;ordered states, the dynamics of the proposed scheme can be modeled as a parametric Markov chain. We show\&nbsp;that the frequencies of different thresholds converge to a steady-state distribution that is concentrated aroundthe optimal choice. Moreover, numerical experiments show that the theoretical performance measures (Fisher\&nbsp;information and Cramer-Rao bounds) can be achieved by a maximum likelihood estimator, which is guaranteed\&nbsp;to find globally optimal solution due to the concavity of the log-likelihood functions. Compared with conventional\&nbsp;image sensors and the strategy that utilizes a constant single-photon threshold considered in previous work, theproposed scheme attains orders of magnitude improvement in terms of sensor dynamic ranges.},
	author = {Hu, C. and Lu, Y.M.}
}
@conference {33211,
	title = {Graph-Based regularization for color image demosaicking},
	booktitle = {Proc.. IEEE International Conference on Image Processing},
	year = {2012},
	month = {Sep.},
	address = {Orlando, FL},
	abstract = {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.},
	author = {Chenhui Hu and Lin Cheng and Yue M. Lu}
}
@conference {27286,
	title = {Optimal spectral sensitivity functions for single sensor color imaging},
	booktitle = {Proc. SPIE Conference on Digital Photography VIII},
	year = {2012},
	month = {Jan.},
	address = {Burlingame},
	abstract = {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.
},
	author = {Z. Sadeghipoor and Lu, Y.M. and S. S{\"u}sstrunk}
}
@conference {27285,
	title = {Uncertainty principles for signals defined on graphs: Bounds and characterizations},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2012},
	note = {See, also, the extended journal version:

A. Agaskar and Y. M. Lu, A Spectral Graph Uncertainty Principle, IEEE Transactions on Information Theory, to appear.},
	month = {Mar.},
	address = {Kyoto},
	abstract = {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.
},
	author = {Agaskar, A. and Lu, Y.M.}
}
@conference {27284,
	title = {Blind estimation and low-rate sampling of sparse MIMO systems with common support},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2012},
	month = {Mar.},
	address = {Kyoto},
	abstract = {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.
},
	author = {Y. Xiong and Lu, Y.M.}
}
@article {27272,
	title = {Multidimensional Filter Banks and Multiscale Geometric Representations},
	journal = {Foundation and Trends in Signal Processing},
	volume = {5},
	number = {3},
	year = {2012},
	pages = {157-264},
	abstract = {Thanks to the explosive growth of sensing devices and capabilities, multidimensional (MD) signals {\textemdash} such as images, videos, multispectral images, light fields, and biomedical data volumes {\textemdash} 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{\"o}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.
},
	author = {M. N. Do and Lu, Y.M.}
}
@article {YangLSV:11,
	title = {Bits from Photons: Oversampled Image Acquisition Using Binary Poisson Statistics},
	journal = {IEEE Transactions on Image Processing},
	volume = {21},
	number = {4},
	year = {2012},
	pages = {1421-1436},
	abstract = {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{\'e}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.},
	url = {http://arxiv.org/abs/1106.0954},
	author = {F. Yang and Lu, Y.M. and L. Sbaiz and M. Vetterli}
}
@conference {27283,
	title = {An uncertainty principle for functions defined on graphs},
	booktitle = {Proc. SPIE Conf. on Wavelets and Sparsity},
	year = {2011},
	note = {See, also, the extended journal version: A. Agaskar and Y. M. Lu, A Spectral Graph Uncertainty Principle, IEEE Transactions on Information Theory, to appear.},
	month = {Aug.},
	address = {San Diego},
	abstract = {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{\textquoteright}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.
},
	author = {Agaskar, A. and Lu, Y.M.}
}
@conference {27273,
	title = {Correlation-Based joint acquisition and demosaicing of visible and near-infrared images},
	booktitle = {Proc. IEEE International Conference on Image Processing},
	year = {2011},
	month = {Sep.},
	address = {Brussels},
	abstract = {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.
},
	author = {Z. Sadeghipoor and Lu, Y.M. and S. Susstrunk}
}
@conference {LuV:11a,
	title = {Sparse spectral factorization: Unicity and reconstruction algorithms},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2011},
	address = {Prague},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Vetterli}
}
@conference {LuDV:11,
	title = {Localizing point sources in diffusion fields from spatiotemporal measurements},
	booktitle = {Proc. Int. Conf. Sampling Theory and applications (SampTA)},
	year = {2011},
	address = {Singapore},
	abstract = {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.
},
	author = {Lu, Y.M. and P. L. Dragotti and M. Vetterli}
}
@conference {RanieriCLV:11,
	title = {Sampling and reconstructing diffusion fields with localized sources},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2011},
	month = {May},
	address = {Prague},
	abstract = {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.
},
	author = {J. Ranieri and A. Chebira and Lu, Y.M. and M. Vetterli}
}
@conference {DokmanicLV:11,
	title = {Can one hear the shape of a room: The 2-D polygonal case},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2011},
	note = {(This paper received the Best Student Paper Award of ICASSP.)
},
	month = {May},
	address = {Prague},
	abstract = {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 {\textemdash} a 1{\textendash}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.
},
	author = {I. Dokmani{\'c} and Lu, Y.M. and M. Vetterli}
}
@conference {27287,
	title = {Learning sparse systems at sub-Nyquist rates: A frequency-domain approach},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2010},
	month = {Apr.},
	address = {Dallas},
	abstract = {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.
},
	author = {M. McCormick and Lu, Y.M. and M. Vetterli}
}
@conference {LuV:10,
	title = {Multichannel sampling with unknown gains and offsets: A fast reconstruction algorithm},
	booktitle = {Proc. Allerton Conference on Communication, Control and Computing.},
	year = {2010},
	month = {Oct.},
	address = {Monticello, IL},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Vetterli}
}
@conference {YangLSV:10,
	title = {An optimal algorithm for reconstructing images from binary measurements},
	booktitle = {Proc. SPIE Conf. Computational Imaging VIII},
	year = {2010},
	month = {Jan.},
	address = {San Jose, CA},
	author = {F. Yang and Lu, Y.M. and L. Sbaiz and M. Vetterli}
}
@article {27227,
	title = {Distributed Sampling of Correlated Signals Linked by Sparse Filtering: Theory and Applications},
	journal = {IEEE Transactions on Signal Processing},
	volume = {58},
	number = {3},
	year = {2010},
	pages = {1095-1109},
	abstract = {We 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.
},
	author = {A. Hormati and O. Roy and Lu, Y.M. and M. Vetterli}
}
@article {27226,
	title = {Demosaicking by Alternating Projections: Theory and Fast One-Step Implementation},
	journal = {IEEE Transactions on Image Processing},
	volume = {19},
	number = {8},
	year = {2010},
	pages = {2085-2098},
	abstract = {Color 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.
},
	url = {http://scholar.harvard.edu/yuelu/software/demosaicking-matlab-code-implementing-fast-demosaicking-algorithm-described-following},
	author = {Lu, Y.M. and M. Karzand and M. Vetterli}
}
@conference {27288,
	title = {Computable Fourier conditions for alias-free sampling and critical sampling.},
	booktitle = {Proc. Int. Conf. Sampling Theory and applications (SampTA)},
	year = {2009},
	address = {Marseille, France},
	abstract = {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.
},
	author = {Lu, Y.M. and M. N. Do and R. Laugesen}
}
@conference {HormatiRLV:09,
	title = {Distributed sensing of signals under a sparse filtering model},
	booktitle = {Proc. 8th International Conference on Sampling Theory and Applications (SampTA)},
	year = {2009},
	address = {Marseille, France},
	abstract = {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.
},
	author = {A. Hormati and O. Roy and Lu, Y.M. and M. Vetterli}
}
@conference {LuFVS:09,
	title = {Designing color filter arrays for the joint capture of visible and near-infrared images},
	booktitle = {Proc. IEEE International Conference on Image Processing},
	year = {2009},
	address = {Cairo, Egypt},
	abstract = {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.
},
	author = {Lu, Y.M. and C. Fredembach and M. Vetterli and S. S{\"u}sstrunk}
}
@conference {CarneiroKGLV:09,
	title = {Assessment of digital surface models for the study of shadowing and radiation over the built environment using wireless sensor network data},
	booktitle = {Proc. 6th International Symposium on Spatial Data Quality},
	year = {2009},
	address = {Newfoundland},
	author = {C. Carneiro and M. Karzand and F. Golay and Lu, Y.M. and M. Vetterli}
}
@conference {LuV:09a,
	title = {Optimal color filter array design: Quantitative conditions and an efficient search procedure},
	booktitle = {Proc. SPIE Electronic Imaging, Digital Photography V},
	year = {2009},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Vetterli}
}
@article {LuDL:09,
	title = {A Computable Fourier Condition Generating Alias-Free Sampling Lattices},
	journal = {IEEE Transactions on Signal Processing},
	volume = {57},
	number = {5},
	year = {2009},
	month = {May},
	pages = {1768{\textendash}1782},
	abstract = {We 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.
},
	author = {Lu, Y.M. and M. N. Do and R. S. Laugesen}
}
@conference {LuV:09d,
	title = {Distributed spatio-temporal sampling of diffusion fields from sparse instantaneous sources},
	booktitle = {Proc. 3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)},
	year = {2009},
	month = {Dec.},
	address = {Aruba},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Vetterli}
}
@conference {LuV:09b,
	title = {Spatial super-resolution of a diffusion field by temporal oversampling in sensor networks},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2009},
	month = {Apr.},
	address = {Taiwan},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Vetterli}
}
@conference {RoyHLV:09,
	title = {Distributed sensing of signals linked by sparse filtering},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2009},
	month = {Apr.},
	address = {Taipei},
	abstract = {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.
},
	author = {O. Roy and A. Hormati and Lu, Y.M. and M. Vetterli}
}
@conference {LuKV:09a,
	title = {Iterative demosaicking accelerated: Theory and fast noniterative implementations},
	booktitle = {Proc. SPIE Conf. Computational Imaging VI},
	year = {2009},
	month = {Jan.},
	address = {San Jose, USA},
	abstract = {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.
},
	author = {Lu, Y.M. and M. Karzand and M. Vetterli}
}
@conference {BarrenetxeaILV:08,
	title = {Assessing the challenges of environmental signal processing through the SensorScope project},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2008},
	pages = {5149{\textendash}5152},
	address = {Las Vegas, USA},
	abstract = {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.
},
	author = {G. Barrenetxea and F. Ingelrest and Lu, Y.M. and M. Vetterli}
}
@article {LuD:07b,
	title = {A Mapping-Based Design for Nonsubsampled Hourglass Filter Banks in Arbitrary Dimensions},
	journal = {IEEE Transactions on Signal Processing},
	volume = {56},
	number = {4},
	year = {2008},
	month = {Apr.},
	pages = {1466-1478},
	abstract = {Multidimensional 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.
},
	author = {Lu, Y.M. and M. N. Do}
}
@article {LuD:07d,
	title = {A Theory for Sampling Signals from a Union of Subspaces},
	journal = {IEEE Transactions on Signal Processing},
	volume = {56},
	number = {6},
	year = {2008},
	month = {Jun.},
	pages = {2334{\textendash}2345},
	abstract = {One 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.
},
	author = {Lu, Y.M. and M. N. Do}
}
@article {LuD:08,
	title = {Sampling Signals from a Union of Subspaces},
	journal = {IEEE Signal Process. Mag., Special Issue on Compressive Sampling},
	volume = {25},
	year = {2008},
	month = {Mar.},
	author = {Lu, Y.M. and M. N. Do}
}
@conference {77971,
	title = {Sampling signals from a union of shift-invariance subspaces},
	booktitle = {Proc. SPIE Conf. on Wavelets Applications in Signal and Image Processing XII},
	year = {2007},
	month = {Aug.},
	address = {San Diego, CA},
	author = {Yue M. Lu and Minh N. Do}
}
@article {27302,
	title = {Multidimensional Directional Filter Banks and Surfacelets},
	journal = {IEEE Transactions on Image Processing},
	volume = {16},
	number = {4},
	year = {2007},
	pages = {918-931},
	abstract = {In 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 \&gt;= 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.
},
	url = {http://lu.seas.harvard.edu/software/surfbox-matlab-and-c-toolbox-implementing-surfacelet-transform-described-following-pa},
	author = {Lu, Y.M. and M. N. Do}
}
@conference {27289,
	title = {Automatic detection of pelvic lymph nodes using multiple MR sequences},
	booktitle = {Proc. SPIE Conference on Medical Imaging},
	year = {2007},
	month = {Feb.},
	address = {San Diego},
	author = {M. Yan and Y. Lu and R. Lu and M. Requardt and T. Moeller and S. Takahashi and J. Barentsz}
}
@conference {LuD:07c,
	title = {Finding optimal integral sampling lattices for a given frequency support in multidimensions},
	booktitle = {Proc. IEEE International Conference on Image Processing},
	year = {2007},
	note = {(This paper received one of the four available Student Paper Awards of ICIP.)
},
	address = {San Antonio, USA},
	abstract = {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.
},
	author = {Lu, Y.M. and M. N. Do}
}
@conference {MuellerLD:07,
	title = {Image interpolation using multiscale geometric representations},
	booktitle = {Proc. SPIE Conf. on Electronic Imaging},
	year = {2007},
	note = {MATLAB code
},
	address = {San Jose, USA},
	abstract = {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.
},
	author = {N. Mueller and Y. Lu and M. N. Do}
}
@conference {27290,
	title = {Video processing using the 3-dimensional surfacelet transform},
	booktitle = {Fortieth Asilomar Conference on Signals, Systems, and Computers},
	year = {2006},
	month = {Nov.},
	address = {Pacific Grove, CA},
	abstract = {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.
},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:06b,
	title = {Multidimensional nonsubsampled hourglass filter banks: Geometry of passband support and filter design},
	booktitle = {Fortieth Asilomar Conference on Signals, Systems, and Computers},
	year = {2006},
	month = {Nov.},
	pages = {406-410},
	address = {Pacific Grove, CA},
	abstract = {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.
},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:06c,
	title = {A new contourlet transform with sharp frequency localization},
	booktitle = {Proc. IEEE International Conference on Image Processing},
	year = {2006},
	note = {(This paper received one of the two available Most Innovative Paper Awards of ICIP.)
MATLAB code},
	month = {Oct.},
	pages = {1629-1632},
	address = {Atlanta, USA},
	abstract = {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{\textquoteright}s) and in visual quality, while with similar computational complexity.},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:05b,
	title = {3-D directional filter banks and surfacelets},
	booktitle = {Proc. of SPIE Conf. on Wavelet Applications in Signal and Image Processing XI},
	year = {2005},
	month = {Aug.},
	pages = {591-601},
	address = {San Diego},
	abstract = {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.
},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:05a,
	title = {The finer directional wavelet transform},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2005},
	month = {Mar.},
	address = {Philadelphia},
	abstract = {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 {\textquotedblleft}add- on{\textquotedblright} 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.
},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:04,
	title = {A geometrical approach to sampling signals with finite rate of innovation},
	booktitle = {Proc. IEEE International Conference on Acoustics, Speech and Signal Processing},
	year = {2004},
	month = {May},
	address = {Montreal, Canada},
	abstract = {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.
},
	author = {Y. Lu and M. N. Do}
}
@conference {LuD:03,
	title = {CRISP-contourlets: A critically-sampled directional multiresultion image representation},
	booktitle = {Proc. of SPIE Conference on Wavelet Applications in Signal and Image Processing X},
	year = {2003},
	month = {Aug.},
	pages = {655-665},
	address = {San Diego, USA},
	abstract = {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.
},
	author = {Y. Lu and M. N. Do}
}
