Abstract A wide range of real-world applications can be formulated as Multi-Agent Path Finding (MAPF) problem, where the goal is to find collision-free paths for multiple agents with individual start and goal locations. State-of-the-art MAPF solvers are mainly centralized and depend on global information, which limits their scalability and flexibility regarding changes or new maps that would require expensive replanning. Multi-agent reinforcement learning (MARL) offers an alternative way of addressing MAPF problems by learning decentralized policies that can generalize over a variety of maps. While there exist some prior works that attempt to connect both areas, the proposed techniques are heavily engineered and very complex due to the integration of many mechanisms that limit generality and are expensive to use. We argue that much simpler and more general approaches are needed to bring the areas of MARL and MAPF closer together with significantly lower costs. In this paper, we propose Confidence-based Auto-Curriculum for Team Update Stability (CACTUS) as a lightweight MARL approach to MAPF. CACTUS defines a simple reverse curriculum scheme, where the goal of each agent is randomly placed within an allocation radius around the agent's start location. The allocation radius increases gradually as all agents improve, which is assessed by a confidence-based measure. In addition, we propose an extension called Confidence- and Conflict-Based Curriculum Learning with Allocation Radius Adaptation (C3LARA), using weighted sampling of goal locations to improve conflict resolution in scenarios of high agent density. We provide a theoretical analysis of the strengths and limitations of CACTUS regarding exploration efficiency and multi-agent coordination. We evaluate CACTUS and C3LARA in various maps of different sizes, obstacle densities, and numbers of agents. Our experiments demonstrate better performance and generalization capabilities than state-of-the-art MARL approaches with less than 600,000 trainable parameters, which is less than 5% of the neural network size of current MARL approaches to MAPF.

The classical iteratively reweighted least-squares (IRLS) algorithm aims to recover an unknown signal from linear measurements by performing a sequence of weighted least squares problems, where the weights are recursively updated at each step. Varieties of this algorithm have been shown to achieve favorable empirical performance and theoretical guarantees for sparse recovery and $\ell_p$-norm minimization. Recently, some preliminary connections have also been made between IRLS and certain types of non-convex linear neural network architectures that are observed to exploit low-dimensional structure in high-dimensional linear models. In this work, we provide a unified asymptotic analysis for a family of algorithms that encompasses IRLS, the recently proposed lin-RFM algorithm (which was motivated by feature learning in neural networks), and the alternating minimization algorithm on linear diagonal neural networks. Our analysis operates in a "batched" setting with i.i.d. Gaussian covariates and shows that, with appropriately chosen reweighting policy, the algorithm can achieve favorable performance in only a handful of iterations. We also extend our results to the case of group-sparse recovery and show that leveraging this structure in the reweighting scheme provably improves test error compared to coordinate-wise reweighting.

In the pathway to 2030 electricity generation decarbonization and 2050 net-zero economies, scalable integration of distributed load can support environmental goals and also help alleviate smart grid operational issues through its electricity market participation. In this work, a novel Stackelberg game theoretic framework is proposed for trading the energy bidirectionally between the demand-response (DR) aggregator and the prosumers (distributed load). This formulation allows for flexible energy arbitrage and additional monetary rewards while ensuring that the prosumers’ desired daily energy demand is met. Then, a scalable (linear with the number of prosumers and the number of learning samples), the decentralized privacy-preserving algorithm is proposed to find approximate equilibria with online sampling and learning of the prosumers’ cumulative best response, which finds applications beyond this energy game. Moreover, cost bounds are provided on the quality of the approximate equilibrium solution. Finally, the real data from the California day-ahead market and the UC Davis campus building energy demands are utilized to demonstrate the efficacy of the proposed framework and the algorithm.

Inverse problems describe the task of recovering an underlying signal of interest given observables. Typically, the observables are related via some non-linear forward model applied to the underlying unknown signal. Inverting the non-linear forward model can be computationally expensive, as it often involves computing and inverting a linearization at a series of estimates. Rather than inverting the physics-based model, we instead train a surrogate forward model (emulator) and leverage modern auto-grad libraries to solve for the input within a classical optimization framework. Current methods to train emulators are done in a black box supervised machine learning fashion and fail to take advantage of any existing knowledge of the forward model. In this article, we propose a simple learned weighted average model that embeds linearizations of the forward model around various reference points into the model itself, explicitly incorporating known physics. Grounding the learned model with physics based linearizations improves the forward modeling accuracy and provides richer physics based gradient information during the inversion process leading to more accurate signal recovery. We demonstrate the efficacy on an ocean acoustic tomography (OAT) example that aims to recover ocean sound speed profile (SSP) variations from acoustic observations (e.g. eigenray arrival times) within simulation of ocean dynamics in the Gulf of Mexico.

The aim of this paper is to improve the understanding of the optimization landscape for policy optimization problems in reinforcement learning. Specifically, we show that the superlevel set of the objective function with respect to the policy parameter is always a connected set both in the tabular setting and under policies represented by a class of neural networks. In addition, we show that the optimization objective as a function of the policy parameter and reward satisfies a stronger “equiconnectedness” property. To our best knowledge, these are novel and previously unknown discoveries. We present an application of the connectedness of these superlevel sets to the derivation of minimax theorems for robust reinforcement learning. We show that any minimax optimization program which is convex on one side and is equiconnected on the other side observes the minimax equality (i.e. has a Nash equilibrium). We find that this exact structure is exhibited by an interesting class of robust reinforcement learning problems under an adversarial reward attack, and the validity of its minimax equality immediately follows. This is the first time such a result is established in the literature.

We present novel analysis and algorithms for solving sparse phase retrieval and sparse principal component analysis (PCA) with convex lifted matrix formulations. The key innovation is a new mixed atomic matrix norm that, when used as regularization, promotes low-rank matrices with sparse factors. We show that convex programs with this atomic norm as a regularizer provide near-optimal sample complexity and error rate guarantees for sparse phase retrieval and sparse PCA. While we do not know how to solve the convex programs exactly with an efficient algorithm, for the phase retrieval case we carefully analyze the program and its dual and thereby derive a practical heuristic algorithm. We show empirically that this practical algorithm performs similarly to existing state-of-the-art algorithms.

We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due to its formulation as a minimax optimization program, a natural approach to solve the problem is to perform gradient descent/ascent with respect to each player in an alternating fashion. However, due to the non-convexity/non-concavity of the underlying objective function, theoretical understandings of this method are limited. In our paper, we consider solving an entropy-regularized variant of the Markov game. The regularization introduces structures into the optimization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We explicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement the analysis with numerical simulations that illustrate the accelerated convergence of the algorithm.

Thomson’s multitaper method estimates the power spectrum of a signal from$N$equally spaced samples by averaging$K$tapered periodograms. Discrete prolate spheroidal sequences (DPSS) are used as tapers since they provide excellent protection against spectral leakage. Thomson’s multitaper method is widely used in applications, but most of the existing theory is qualitative or asymptotic. Furthermore, many practitioners use a DPSS bandwidth$W$and number of tapers that are smaller than what the theory suggests is optimal because the computational requirements increase with the number of tapers. We revisit Thomson’s multitaper method from a linear algebra perspective involving subspace projections. This provides additional insight and helps us establish nonasymptotic bounds on some statistical properties of the multitaper spectral estimate, which are similar to existing asymptotic results. We show using$K=2NW-O(\log (NW))$tapers instead of the traditional$2NW-O(1)$tapers better protects against spectral leakage, especially when the power spectrum has a high dynamic range. Our perspective also allows us to derive an$\epsilon $-approximation to the multitaper spectral estimate which can be evaluated on a grid of frequencies using$O\left({\log (NW)\log \tfrac {1}{ \epsilon }}\right)$FFTs instead of$K=O(NW)$FFTs. This is useful in problems where many samples are taken, and thus, using many tapers is desirable.

We develop a mathematical framework for solving multi-task reinforcement learning (MTRL) problems based on a type of policy gradient method. The goal in MTRL is to learn a common policy that operates effectively in different environments; these environments have similar (or overlapping) state spaces, but have different rewards and dynamics. We highlight two fundamental challenges in MTRL that are not present in its single task counterpart, and illustrate them with simple examples. We then develop a decentralized entropyregularized policy gradient method for solving the MTRL problem, and study its finite-time convergence rate. We demonstrate the effectiveness of the proposed method using a series of numerical experiments. These experiments range from small-scale "GridWorld" problems that readily demonstrate the trade-offs involved in multi-task learning to large-scale problems, where common policies are learned to navigate an airborne drone in multiple (simulated) environments.

OBJECTIVE: The COVID-19 pandemic has created many challenges that need immediate attention. Various epidemiological and deep learning models have been developed to predict the COVID-19 outbreak, but all have limitations that affect the accuracy and robustness of the predictions. Our method aims at addressing these limitations and making earlier and more accurate pandemic outbreak predictions by (1) using patients' EHR data from different counties and states that encode local disease status and medical resource utilization condition; (2) considering demographic similarity and geographical proximity between locations; and (3) integrating pandemic transmission dynamics into deep learning models. MATERIALS AND METHODS: We proposed a spatio-temporal attention network (STAN) for pandemic prediction. It uses an attention-based graph convolutional network to capture geographical and temporal trends and predict the number of cases for a fixed number of days into the future. We also designed a physical law-based loss term for enhancing long-term prediction. STAN was tested using both massive real-world patient data and open source COVID-19 statistics provided by Johns Hopkins university across all U.S. counties. RESULTS: STAN outperforms epidemiological modeling methods such as SIR and SEIR and deep learning models on both long-term and short-term predictions, achieving up to 87% lower mean squared error compared to the best baseline prediction model. CONCLUSIONS: By using information from real-world patient data and geographical data, STAN can better capture the disease status and medical resource utilization information and thus provides more accurate pandemic modeling. With pandemic transmission law based regularization, STAN also achieves good long-term prediction performance.

The increase in the number of edge devices has led to the emergence of edge computing where the computations are performed on the device. In recent years, deep neural networks (DNNs) have become the state-of-the-art method in a broad range of applications, from image recognition, to cognitive tasks to control. However, neural network models are typically large and computationally expensive and therefore not deployable on power and memory constrained edge devices. Sparsification techniques have been proposed to reduce the memory foot-print of neural network models. However, they typically lead to substantial hardware and memory overhead. In this article, we propose a hardware-aware pruning method using linear feedback shift register (LFSRs) to generate the locations of non-zero weights in real-time during inference. We call this LFSR-generated pseudorandom sequence based sparsity (LGPS) technique. We explore two different architectures for our hardware-friendly LGPS technique, based on (1) row/column indexing with LFSRs and (2) column-wise indexing with nested LFSRs, respectively. Using the proposed method, we present a total saving of energy and area up to 37.47% and 49.93% respectively and speed up of 1.53× w.r.t the baseline pruning method, for the VGG-16 network on down-sampled ImageNet.

We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching, where at any given point, only part of the data matrix is available. This corresponds to a block diagonal structure on the sketching matrix. We show that, under mild conditions, block diagonal sketching matrices require only $O(\sr / \epsilon^2)$ and $O(\sd_{\lambda}/\epsilon)$ total sample complexity for matrix multiplication and ridge regression, respectively. This matches the state-of-the-art bounds that are obtained using global sketching matrices. The localized nature of sketching considered allows for different parts of the data matrix to be sketched independently and hence is more amenable to computation in distributed and streaming settings and results in a smaller memory and computational footprint.

Deep neural networks (DNNs) have been emerged as the state-of-the-art algorithms in broad range of applications. To reduce the memory foot-print of DNNs, in particular for embedded applications, sparsification techniques have been proposed. Unfortunately, these techniques come with a large hardware overhead. In this paper, we present a hardware-aware pruning method where the locations of non-zero weights are derived in real-time from a Linear Feedback Shift Registers (LFSRs). Using the proposed method, we demonstrate a total saving of energy and area up to 63.96% and 64.23% for VGG-16 network on down-sampled ImageNet, respectively for iso-compression-rate and iso-accuracy.

We consider the theory of regression on a manifold using reproducing kernel Hilbert space methods. Manifold models arise in a wide variety of modern machine learning problems, and our goal is to help understand the effectiveness of various implicit and explicit dimensionality-reduction methods that exploit manifold structure. Our first key contribution is to establish a novel nonasymptotic version of the Weyl law from differential geometry. From this we are able to show that certain spaces of smooth functions on a manifold are effectively finite-dimensional, with a complexity that scales according to the manifold dimension rather than any ambient data dimension. Finally, we show that given (potentially noisy) function values taken uniformly at random over a manifold, a kernel regression estimator (derived from the spectral decomposition of the manifold) yields minimax-optimal error bounds that are controlled by the effective dimension.

We study the problem of actively imaging a range-limited far-field scene using an antenna array. We describe how the range limit imposes structure in the measurements across multiple wavelengths. This structure allows us to introduce a novel trade-off: the number of spatial array measurements (i.e., beams that have to be formed) can be reduced to be significantly lower than the number array elements if the scene is illuminated with a broadband source. To take advantage of this trade-off, we use a small number of “generic” linear combinations of the array outputs, instead of the phase offsets used in conventional beamforming. We provide theoretical justification for the proposed trade-off without making any strong structural assumptions on the target scene (such as sparsity) except that it is range-limited. In proving our theoretical results, we take inspiration from the sketching literature. We also provide simulation results to establish the merit of the proposed signal acquisition strategy. Our proposed method results in a reduction in the number of required spatial measurements in an array imaging system and hence can directly impact their speed and cost of operation.

We propose several sampling architectures for the efficient acquisition of an ensemble of correlated signals. We show that without prior knowledge of the correlation structure, each of our architectures (under different sets of assumptions) can acquire the ensemble at a sub-Nyquist rate. Prior to sampling, the analog signals are diversified using simple, implementable components. The diversification is achieved by injecting types of “structured randomness” into the ensemble, the result of which is subsampled. For reconstruction, the ensemble is modeled as a low-rank matrix that we have observed through an (undetermined) set of linear equations. Our main results show that this matrix can be recovered using a convex program when the total number of samples is on the order of the intrinsic degree of freedom of the ensemble - the more heavily correlated the ensemble, the fewer samples are needed. To motivate this study, we discuss how such ensembles arise in the context of array processing.

Optimization problems form the basis of a wide gamut of computationally challenging tasks in signal processing, machine learning, resource planning and so on. Out of these, convex optimization, and in particular least square optimization, covers a vast majority; and recent advances in iterative algorithms to solve such problems of large dimensions have gained traction. Multi-core designs with systolic or semi-systolic architectures can be a key enabler for implementing discrete dynamical systems and realize massively scalable architectures to solve such optimization algorithms. In this paper, we present a platform architecture implemented in programmable FPGA hardware to solve a template problem in distributed optimization, namely signal reconstruction from non-uniform sampling. This is a quintessential problem with wide-spread applications in signal processing, computational imaging etc. We expect such an architectural exploration to open up promising opportunities to solve distributed optimizations that are becoming increasingly important in real-world applications. The complete system design, mapping and optimization into an FPGA architecture as well as analysis of convergence and scalability have been presented.

Deep learning models have significantly improved the visual quality and accuracy on compressive sensing recovery. In this paper, we propose an algorithm for signal reconstruction from compressed measurements with image priors captured by a generative model. We search and constrain on latent variable space to make the method stable when the number of compressed measurements is extremely limited. We show that, by exploiting certain structures of the latent variables, the proposed method produces improved reconstruction accuracy and preserves realistic and non-smooth features in the image. Our algorithm achieves high computation speed by projecting between the original signal space and the latent variable space in an alternating fashion.

We study the policy evaluation problem in multi-agent reinforcement learning. In this problem, a group of agents works cooperatively to evaluate the value function for the global discounted accumulative reward problem, which is composed of local rewards observed by the agents. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed consensus-based variant of the popular temporal difference learning algorithm TD(0). While distributed reinforcement learning algorithms have been presented in the literature, almost nothing is known about their convergence rate. Our main contribution is providing a finite-time analysis for the convergence of the distributed TD(0) algorithm. We do this when the communication network between the agents is time-varying in general. We obtain an explicit upper bound on the rate of convergence of this algorithm as a function of the network topology and the discount factor. Our results mirror what we would expect from using distributed stochastic gradient descent for solving convex optimization problems.

We address a low-rank matrix recovery problem where each column of a rank-r matrix X of size (d1,d2) is compressed beyond the point of recovery to size L with L << d1. Leveraging the joint structure between the columns, we propose a method to recover the matrix to within an epsilon relative error in the Frobenius norm from a total of O(r(d1 + d2)\log^6(d1 + d2)/\epsilon^2) observations. This guarantee holds uniformly for all incoherent matrices of rank r. In our method, we propose to use a novel matrix norm called the mixed-norm along with the maximum l2 norm of the columns to design a novel convex relaxation for low-rank recovery that is tailored to our observation model. We also show that our proposed mixed-norm, the standard nuclear norm, and the max-norm are particular instances of convex regularization of low-rankness via tensor norms. Finally, we provide a scalable ADMM algorithm for the mixed-norm based method and demonstrate its empirical performance via large-scale simulations.

We study the problem of passive imaging through convolutive channels. A scene is illuminated with an unknown, unstructured source, and the measured response is the convolution of this source with multiple channel responses, each of which is time-limited. Spectral methods based on the commutativity of convolution, first proposed and analyzed in the 1990s, provide an elegant mathematical framework for attacking this problem. However, these now classical methods are very sensitive to noise, especially when working from relatively small sample sizes. In this paper, we show that a linear subspace model on the coefficients of the impulse responses of the channels can make this problem well-posed. We derive nonasymptotic error bounds for the generic subspace model by analyzing the spectral gap of the cross-correlation (CC) matrix of the channels relative to the perturbation introduced by noise. Numerical results show that this modified spectral method offers significant improvements over the classical method and outperforms other competing methods for multichannel blind deconvolution.

Bandlimiting and timelimiting operators play a fundamental role in analyzing bandlimited signals that are approximately timelimited (or vice versa). In this letter, we consider a time-frequency (in the discrete Fourier transform (DFT) domain) limiting operator whose eigenvectors are known as the periodic discrete prolate spheroidal sequences. We establish new nonasymptotic results on the eigenvalue distribution of this operator. As a byproduct, we also characterize the eigenvalue distribution of a set of submatrices of the DFT matrix, which is of independent interest.

This paper presents an ultralow power smart camera with gesture detection. Low power is achieved by directly extracting gesture features from the compressed measurements, which are the block averages and the linear combinations of the image sensor's pixel values. We present two classifier techniques to allow low computational and storage requirements. The system has been implemented on an analog devices BlackFin ULP vision processor. By enabling ultralow energy consumption, we demonstrate that the system is powered by ambient light harvested through photovoltaic cells whose output is regulated by TI's dc-dc buck converter with maximum power point tracking. Measured data reveals that with only 400 compressed measurements (768× compression ratio) per frame, the system is able to recognize key wake-up gestures with greater than 80% accuracy and only 95mJ of energy per frame. Owing to its fully self-powered operation, the proposed system can find wide applications in “always-on” vision systems, such as in surveillance, robotics, and consumer electronics with touch-less operation.

We present a general method for extracting a region from an image (or 3D object) that can be expressed, or approximated, by taking unions and set differences from a collection of template shapes in a dictionary. We build on recent work that shows how this geometric problem can be recast in the language of linear algebra, with set operations on shapes translated into linear combinations of vectors, and solved using convex programming. This paper presents a set of sufficient conditions for which this convex program returns the "correct" shape. These conditions are robust in that they can account for the shapes that have indistinct boundaries, or model mismatch between the shapes in the dictionary and the target region in the image. We also present two different methods for solving the convex extraction program. The first method simply recasts the problem as a linear program, while the second uses the alternating direction method of multipliers with a series of easily computed proximal operators. We present a number of numerical experiments that use the framework to perform image segmentation, optical character recognition, and find multi-resolution geometrical descriptions of 3D objects.

We consider the multichannel blind deconvolution problem where we observe the output of multiple channels that are all excited with the same unknown input. From these observations, we wish to estimate the impulse responses of each of the channels. We show that this problem is well-posed if the channels follow a bilinear model where the ensemble of channel responses is modeled as lying in a low-dimensional subspace but with each channel modulated by an independent gain. Under this model, we show how the channel estimates can be found by minimizing a quadratic function over a non-convex set. We analyze two methods for solving this non-convex program, and provide performance guarantees for each. The first is a method of alternating eigenvectors that breaks the program down into a series of eigenvalue problems. The second is a truncated power iteration, which can roughly be interpreted as a method for finding the largest eigenvector of a symmetric matrix with the additional constraint that it adheres to our bilinear model. As with most non-convex optimization algorithms, the performance of both of these algorithms is highly dependent on having a good starting point. We show how such a starting point can be constructed from the channel measurements. Our performance guarantees are non-asymptotic, and provide a sufficient condition on the number of samples observed per channel in order to guarantee channel estimates of certain accuracy. Our analysis uses a model with a “generic” subspace that is drawn at random, and we show the performance bounds hold with high probability. Mathematically, the key estimates are derived by quantifying how well the eigenvectors of certain random matrices approximate the eigenvectors of their mean. We also present a series of numerical results demonstrating that the empirical performance is consistent with the presented theory.

We propose a flexible convex relaxation for the phase retrieval problem that operates in the natural domain of the signal. Therefore, we avoid the prohibitive computational cost associated with “lifting” and semidefinite programming (SDP) in methods such as PhaseLift and compete with recently developed non-convex techniques for phase retrieval. We relax the quadratic equations for phaseless measurements to inequality constraints each of which representing a symmetric “slab”. Through a simple convex program, our proposed estimator finds an extreme point of the intersection of these slabs that is best aligned with a given anchor vector. We characterize geometric conditions that certify success of the proposed estimator. Furthermore, using classic results in statistical learning theory, we show that for random measurements the geometric certificates hold with high probability at an optimal sample complexity. Phase transition of our estimator is evaluated through simulations. Our numerical experiments also suggest that the proposed method can solve phase retrieval problems with coded diffraction measurements as well.

We review advances in sampling theory since the turn of the century, with a special emphasis on how basis decompositions have allowed us to pose and analyze sampling problems more through the lens of linear algebra, than through the traditional lens of filtering and Fourier decompositions. This new framework also allows us to incorporate nonlinear (sparse) signal models into the signal reconstruction process using optimization.

We propose a novel appearance-based gesture recognition algorithm using compressed domain signal processing techniques. Gesture features are extracted directly from the compressed measurements, which are the block averages and the coded linear combinations of the image sensor's pixel values. We also improve both the computational efficiency and the memory requirement of the previous DTW-based K-NN gesture classifiers. Both simulation testing and hardware implementation strongly support the proposed algorithm.

In this paper, we provide a dictionary for representing the discrete vector one obtains when collecting a finite set of uniform samples from a baseband analog signal. Like the discrete prolate spheroidal sequences (DPSS's), the proposed orthogonal basis compactly captures most of the energy in oversampled bandlimited signals. The complexity of computing the representation of a signal using the proposed dictionary is comparable to the FFT, which is much less than that involving the DPSS basis. We also give non-asymptotic results to guarantee that the proposed basis not only provides a very high degree of approximation accuracy in an MSE sense for bandlimited sample vectors, but also that it can provide high-quality approximations of all sampled sinusoids within the band of interest.

We introduce and analyze a new technique for model reduction for deep neural networks. While large networks are theoretically capable of learning arbitrarily complex models, overfitting and model redundancy negatively affects the prediction accuracy and model variance. Our Net-Trim algorithm prunes (sparsifies) a trained network layer-wise, removing connections at each layer by solving a convex optimization program. This program seeks a sparse set of weights at each layer that keeps the layer inputs and outputs consistent with the originally trained model. The algorithms and associated analysis are applicable to neural networks operating with the rectified linear unit (ReLU) as the nonlinear activation. We present both parallel and cascade versions of the algorithm. While the latter can achieve slightly simpler models with the same generalization performance, the former can be computed in a distributed manner. In both cases, Net-Trim significantly reduces the number of connections in the network, while also providing enough regularization to slightly reduce the generalization error. We also provide a mathematical analysis of the consistency between the initial network and the retrained model. To analyze the model sample complexity, we derive the general sufficient conditions for the recovery of a sparse transform matrix. For a single layer taking independent Gaussian random vectors of length $N$ as inputs, we show that if the network response can be described using a maximum number of $s$ non-zero weights per node, these weights can be learned from $\mathcal{O}(s\log N)$ samples.

In this paper we propose an energy-efficient camera-based gesture recognition system powered by light energy for "always on" applications. Low energy consumption is achieved by directly extracting gesture features from the compressed measurements, which are the block averages and the linear combinations of the image sensor's pixel values. The gestures are recognized using a nearest-neighbour (NN) classifier followed by Dynamic Time Warping (DTW). The system has been implemented on an Analog Devices Black Fin ULP vision processor and powered by PV cells whose output is regulated by TI's DC-DC buck converter with Maximum Power Point Tracking (MPPT). Measured data reveals that with only 400 compressed measurements (768x compression ratio) per frame, the system is able to recognize key wake-up gestures with greater than 80% accuracy and only 95mJ of energy per frame. Owing to its fully self-powered operation, the proposed system can find wide applications in "always-on" vision systems such as in surveillance, robotics and consumer electronics with touch-less operation.

We propose a robust and efficient approach to the problem of compressive phase retrieval in which the goal is to reconstruct a sparse vector from the magnitude of a number of its linear measurements. The proposed framework relies on constrained sensing vectors and a two-stage reconstruction method that consists of two standard convex programs that are solved sequentially.In recent years, various methods are proposed for compressive phase retrieval, but they have suboptimal sample complexity or lack robustness guarantees. The main obstacle has been that there is no straightforward convex relaxations for the type of structure in the target. Given a set of underdetermined measurements, there is a standard framework for recovering a sparse matrix, and a standard framework for recovering a low-rank matrix. However, a general, efficient method for recovering a jointly sparse and low-rank matrix has remained elusive.Deviating from the models with generic measurements, in this paper we show that if the sensing vectors are chosen at random from an incoherent subspace, then the low-rank and sparse structures of the target signal can be effectively decoupled. We show that a recovery algorithm that consists of a low-rank recovery stage followed by a sparse recovery stage will produce an accurate estimate of the target when the number of measurements is $\mathsf{O}(k\,\log\frac{d}{k})$, where $k$ and $d$ denote the sparsity level and the dimension of the input signal. We also evaluate the algorithm through numerical simulation.

We propose a new shape-based modeling technique for applications in imaging problems. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right dictionary elements and geometrically composing them through basic set operations to characterize desired regions in an image. This is a combinatorial problem solving which requires an exhaustive search among a large number of possibilities. We propose a convex relaxation to the problem to make it computationally tractable. We take some major steps towards the analysis of the proposed convex program and characterizing its minimizers. Applications vary from shape-based characterization, object tracking, optical character recognition, and shape recovery in occlusion to other disciplines such as the geometric packing problem.

In this paper we analyze the blind deconvolution of an image and an unknown blur in a coded imaging system. The measurements consist of subsampled convolution of an unknown blurring kernel with multiple random binary modulations (coded masks) of the image. To perform the deconvolution, we consider a standard lifting of the image and the blurring kernel that transforms the measurements into a set of linear equations of the matrix formed by their outer product. Any rank-one solution to this system of equations provides a valid pair of an image and a blur. We first express the necessary and sufficient conditions for the uniqueness of a rank-one solution under some additional assumptions (uniform subsampling and no limit on the number of coded masks). These conditions are a special case of a previously established result regarding identifiability in the matrix completion problem. We also characterize a low-dimensional subspace model for the blur kernel that is sufficient to guarantee identifiability, including the interesting instance of “bandpass” blur kernels. Next, assuming the bandpass model for the blur kernel, we show that the image and the blur kernel can be found using nuclear norm minimization. Our main results show that recovery is achieved (with high probability) when the number of masks is on the order of $\mu\log^{2}L\,\log\frac{Le}{\mu}\,\log\log(N+1),$ where $\mu$ is the coherence of the blur, $L$ is the dimension of the image, and $N$ is the number of measured samples per mask.

We present a general architecture for the acquisition of ensembles of correlated signals. The signals are multiplexed onto a single line by mixing each one against a different code and then adding them together, and the resulting signal is sampled at a high rate. We show that if the M signals, each band limited to W/2 Hz, can be approximated by a superposition of R <; M underlying signals, then the ensemble can be recovered by sampling at a rate within a logarithmic factor of RW, as compared with the cumulative Nyquist rate of MW. This sampling theorem shows that the correlation structure of the signal ensemble can be exploited in the acquisition process even though it is unknown a priori. The reconstruction of the ensemble is recast as a low-rank matrix recovery problem from linear measurements. The architectures we are considering impose a certain type of structure on the linear operators. Although our results depend on the mixing forms being random, this imposed structure results in a very different type of random projection than those analyzed in the low-rank recovery literature to date.

Recovering static signals from compressed measurements is an important problem that has been extensively studied in modern signal processing. However, only recently have methods been proposed to tackle the problem of recovering a time-varying sequence from streaming online compressed measurements. In this paper, we study the capacity of the standard iterative soft-thresholding algorithm (ISTA) to perform this task in real-time. In previous work, ISTA has been shown to recover static sparse signals. The present paper demonstrates its ability to perform this recovery online in the dynamical setting where measurements are constantly streaming. Our analysis shows that the ℓ2-distance between the output and the target signal decays according to a linear rate, and is supported by simulations on synthetic and real data.

In this paper, the robust off-grid recovery of the compressed signals with atomic norm-regularized least-squares problem is studied. The aim of the recovery is to reconstruct the original signal and to detect its off-grid support set. The general optimality conditions for the solution to this problem and its dual problem are proposed and discussed. A method based on dual certification to detect the support set is introduced and proved to be effective. As a specific case, the target signal is further assumed to have unknown line spectrum. Then the problem is also an estimation of a low dimensional subspace which is indexed by continuous parameters, yet the dimension itself is unknown. Under these presumptions, the squared-error of the reconstruction is derived. Finally, numerical experiments are demonstrated in such case to validate the effectiveness of the method and the plausibility of the theory.

Error estimating codes (EEC) have recently been proposed for measuring the bit error rate (BER) in packets transmitted over wireless links. They however can provide such measurements only when there are no insertion and deletion errors, which could occur in various wireless network environments. In this work, we propose ``idEEC'', the first technique that can do so even in the presence of insertion and deletion errors. We show that idEEC is provable robust under most bit insertion and deletion scenarios, provided insertion/deletion errors occur with much lower probability than bit flipping errors. Our idEEC design can build upon any existing EEC scheme. The basic idea of the idEEC encoding is to divide the packet into a number of segments, each of which is encoded using the underlying EEC scheme. The basic idea of the idEEC decoding is to divide the packet into a few slices in a randomized manner -- each of which may contain several segments -- and then try to identify a slice that has no insertion and deletion errors in it (called a ``clean slice''). Once such a clean slice is found, it is removed from the packet for later processing, and this ``randomized divide and search'' procedure will be iteratively performed on the rest of the packet until no more clean slices can be found. The BER will then be estimated from all the clean slices discovered through all the iterations. A careful analysis of the accuracy guarantees of the idEEC decoding is provided, and the efficacy of idEEC is further validated by simulation experiments.

We consider the problem of recovering two unknown vectors, w and x, of length L from their circular convolution. We make the structural assumption that the two vectors are members of known subspaces, one with dimension N and the other with dimension K. Although the observed convolution is nonlinear in both w and x, it is linear in the rank-1 matrix formed by their outer product wx*. This observation allows us to recast the deconvolution problem as low-rank matrix recovery problem from linear measurements, whose natural convex relaxation is a nuclear norm minimization program. We prove the effectiveness of this relaxation by showing that, for “generic” signals, the program can deconvolve w and x exactly when the maximum of N and K is almost on the order of L. That is, we show that if x is drawn from a random subspace of dimension N, and w is a vector in a subspace of dimension K whose basis vectors are spread out in the frequency domain, then nuclear norm minimization recovers wx* without error. We discuss this result in the context of blind channel estimation in communications. If we have a message of length N, which we code using a random L x N coding matrix, and the encoded message travels through an unknown linear time-invariant channel of maximum length K, then the receiver can recover both the channel response and the message when L ≳ N + K, to within constant and log factors.

This document provides a correction to the proof of the theorem establishing the exponential speed of convergence of the Locally Competitive Algorithm (LCA) in the paper “Convergence and Rate Analysis of Neural Networks for Sparse Approximation.”

In this work, we present POUTINE, a novel estimator of the auto-correlation function (or more generally, the cross-correlation function) of ergodic stationary signals, an important task in a variety of applications. This estimator sparsely and non-adaptively samples the process via Bernoulli selection, generalizing the classical estimator in a natural way, and offering significant sampling reductions while sacrificing a modest degree of accuracy. Both the mean and variance of our estimator are explicitly analyzed, and in particular, we show that POUTINE gives an unbiased estimate of the classical estimator, which in turn gives an unbiased estimate of the underlying second-order statistics of interest. Furthermore, we show that POUTINE is a consistent estimator with variance approaching zero asymptotically. We demonstrate favorable performance of this approach for a simple stochastic process.

Sparse approximation is an optimization program that produces state-of-the-art results in many applications in signal processing and engineering. To deploy this approach in real-time, it is necessary to develop faster solvers than are currently available in digital. The Locally Competitive Algorithm (LCA) is a dynamical system designed to solve the class of sparse approximation problems in continuous time. But before implementing this network in analog VLSI, it is essential to provide performance guarantees. This paper presents new results on the convergence of the LCA neural network. Using recently-developed methods that make use of the Łojasiewicz inequality for nonsmooth functions, we prove that the output and state trajectories converge to a single fixed point. This improves on previous results by guaranteeing convergence to a singleton even when the optimization program has infinitely many and non-isolated solution points.

This paper introduces a new shape-based image reconstruction technique applicable to a large class of imaging problems formulated in a variational sense. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right elements and geometrically composing them through basic set operations to characterize desired regions in the image. This combinatorial problem can be relaxed and then solved using classical descent methods. The main component of this relaxation is forming certain compactly supported functions which we call “knolls” and reformulating the shape representation as a basis expansion in terms of such functions. To select suitable elements of the dictionary, our problem ultimately reduces to solving a nonlinear program with sparsity constraints. We provide a new sparse nonlinear reconstruction technique to approach this problem. The performance of the proposed technique is demonstrated with some standard imaging problems including image segmentation, X-ray tomography, and diffusive tomography.

In this paper, we study a simple correlation-based strategy for estimating the unknown delay and amplitude of a signal based on a small number of noisy, randomly chosen frequency-domain samples. We model the output of this “compressive matched filter” as a random process whose mean equals the scaled, shifted autocorrelation function of the template signal. Using tools from the theory of empirical processes, we prove that the expected maximum deviation of this process from its mean decreases sharply as the number of measurements increases, and we also derive a probabilistic tail bound on the maximum deviation. Putting all of this together, we bound the minimum number of measurements required to guarantee that the empirical maximum of this random process occurs sufficiently close to the true peak of its mean function. We conclude that for broad classes of signals, this compressive matched filter will successfully estimate the unknown delay (with high probability and within a prescribed tolerance) using a number of random frequency-domain samples that scales inversely with the signal-to-noise ratio and only logarithmically in the observation bandwidth and the possible range of delays.

In this work we present an efficient method to recover images that have been corrupted by a certain class of image filters. For this class of filters, the image degradation process is described by a linear system of equations involving a two-level Toeplitz matrix with triangular structure on either the block or subblock level. This type of structure has algebraic properties that allow us to adapt “superfast” methods for Toeplitz matrix inversion to the two-level case. Our novel two-level superfast algorithm performs the majority of its calculation with the Fast Fourier Transform and allows us to invert an N × N matrix in O(N log N) with reasonable overhead constant. To demonstrate the power of the algorithm we deblur severely corrupted images in short execution times.

We present an analysis of the Locally Competitive Algorithm (LCA), which is a Hopfield-style neural network that efficiently solves sparse approximation problems (e.g., approximating a vector from a dictionary using just a few nonzero coefficients). This class of problems plays a significant role in both theories of neural coding and applications in signal processing. However, the LCA lacks analysis of its convergence properties, and previous results on neural networks for nonsmooth optimization do not apply to the specifics of the LCA architecture. We show that the LCA has desirable convergence properties, such as stability and global convergence to the optimum of the objective function when it is unique. Under some mild conditions, the support of the solution is also proven to be reached in finite time. Furthermore, some restrictions on the problem specifics allow us to characterize the convergence rate of the system by showing that the LCA converges exponentially fast with an analytically bounded convergence rate. We support our analysis with several illustrative simulations.

This paper presents an algorithm for an ℓ1-regularized Kalman filter. Given observations of a discrete-time linear dynamical system with sparse errors in the state evolution, we estimate the state sequence by solving an optimization algorithm that balances fidelity to the measurements (measured by the standard ℓ2norm) against the sparsity of the innovations (measured using the ℓ1norm). We also derive an efficient algorithm for updating the estimate as the system evolves. This dynamic updating algorithm uses a homotopy scheme that tracks the solution as new measurements are slowly worked into the system and old measurements are slowly removed. The effective cost of adding new measurements is a number of low-rank updates to the solution of a linear system of equations that is roughly proportional to the joint sparsity of all the innovations in the time interval of interest.

When available, vanishing points in a scene are a key factor in effectively recovering absolute camera orientation, thus simplifying the structure-from-motion problem. We present a novel method for estimating vanishing points without explicitly detecting line features. This approach first maps images into line-space with a filtered- Radon operator, allowing subtle line textures to contribute, and improving the angular resolution of broken or occluded segments of the same line. Then, we use a robust coarse-to-fine method to jointly estimate the three vanishing points. We evaluate our method on video sequences, demonstrating robustness to clutter lines as well as the ability to effectively utilize subtle edge-texture information.

The Fast Fourier Transform (FFT) allows the Discrete Time Fourier Transform (DTFT) to be efficiently sampled on a uniform grid in frequency. In many applications, including Magnetic Resonance Imaging (MRI), uniform measurements are undesirable or impractical. Non-equispaced measurements in the Fourier domain are typically obtained through methods that use FFT values to interpolate the DTFT at off-grid locations. These algorithms, known as NUFFTs, are prohibitively expensive for large data sets in 3-D because of the interpolation cost. This paper proposes an exact transform called the SpiralFFT capable of sampling the DTFT on spiral patterns in 3-D frequency space. The SpiralFFT uses spiral structure to replace 3-D calculations with 1-D FFTs and chirp Z-transforms (CZTs). Simulations compare the SpiralFFT with a NUFFT algorithm on a realistic 3-D MRI data set. Results show that the SpiralFFT exhibits a factor of 8 increase in speed for comparable accuracy, and 8 orders of magnitude improvement in accuracy for comparable execution time. These results demonstrate the potential use of the SpiralFFT in spiral MRI to improve reconstruction speed and quality.

This paper demonstrates a computational image sensor capable of implementing compressive sensing operations. Instead of sensing raw pixel data, this image sensor projects the image onto a separable 2-D basis set and measures the corresponding expansion coefficients. The inner products are computed in the analog domain using a computational focal plane and an analog vector-matrix multiplier (VMM). This is more than mere postprocessing, as the processing circuity is integrated as part of the sensing circuity itself. We implement compressive imaging on the sensor by using pseudorandom vectors called noiselets for the measurement basis. This choice allows us to reconstruct the image from only a small percentage of the transform coefficients. This effectively compresses the image without any digital computation and reduces the throughput of the analog-to-digital converter (ADC). The reduction in throughput has the potential to reduce power consumption and increase the frame rate. The general architecture and a detailed circuit implementation of the image sensor are discussed. We also present experimental results that demonstrate the advantages of using the sensor for compressive imaging rather than more traditional coded imaging strategies.

Wideband analog signals push contemporary analog-to-digital conversion (ADC) systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient because the signals of interest contain only a small number of significant frequencies relative to the band limit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its band limit in hertz. Simulations suggest that the random demodulator requires just O(K log(W/K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W hertz. In contrast to Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. This paper provides a detailed theoretical analysis of the system's performance that supports the empirical observations.

This paper demonstrates that convolution with random waveform followed by random time-domain subsampling is a universally efficient compressive sensing strategy. We show that an n-dimensional signal which is S-sparse in any fixed orthonormal representation can be recovered from $m\gtrsim S\log n$ samples from its convolution with a pulse whose Fourier transform has unit magnitude and random phase at all frequencies. The time-domain subsampling can be done in one of two ways: in the first, we simply observe m samples of the random convolution; in the second, we break the random convolution into m blocks and summarize each with a single randomized sum. We also discuss several imaging applications where convolution with a random pulse allows us to superresolve fine-scale features, allowing us to recover high-resolution signals from low-resolution measurements.

Compressive Sensing (CS) uses a relatively small number of non-traditional samples in the form of randomized projections to reconstruct sparse or compressible signals. The Hough transform is often used to find lines and other parameterized shapes in images. This paper shows how CS can be used to find parameterized shapes in images, by exploiting sparseness in the Hough transform domain. The utility of the CS-based method is demonstrated for finding lines and circles in noisy images, and then examples of processing GPR and seismic data for tunnel detection are presented.

This paper discusses the application of a computational image sensor, capable of performing separable 2-D transforms on images in the analog domain, to compressive sensing. Instead of sensing and transmitting raw pixel data, this image sensor first projects the image onto a separable 2-D basis set. The inner products computed in these projections are computed in the analog domain using a computational focal-plane and a computational analog vector-matrix multiplier. Since this operation is performed in the analog domain, components such as the analog-to-digital converters can be taxed less when a only subset of correlations are performed. Compressed sensing theory prescribes the use of a pseudo-random, incomplete basis set, allowing for sampling at less than the Nyquist rate. This can reduce power consumption or increase frame rate.

There is a significant amount of redundancy between video frames or images that can be explained by considering these observations as samples of a light field function. By using a compact depth- augmented representation for such a light field function, it may even be possible to tie-together inter-frame dependencies in a more meaningful way than conventional 2-D intensity based motion compensation methods. We propose a depth-augmented layered orthographic light field representation and show how it may be constructed from actual data at a basic level as the solution to an over-determined linear inverse problem. We finally demonstrate the potential utility of such information in video coding with a compression example when this light field side information is given as a simple texture map.

We address the problem of encoding signals which are sparse, i.e. signals that are concentrated on a set of small support. Mathematically, such signals are modeled as elements in the /spl lscr//sub p/ ball for some p < 1. We describe a strategy for encoding elements of the /spl lscr//sub p/ ball which is universal in that 1) the encoding procedure is completely generic, and does not depend on p (the sparsity of the signal), and 2) it achieves near-optimal minimax performance simultaneously for all p < 1. What makes our coding procedure unique is that it requires only a limited number of nonadaptive measurements of the underlying sparse signal; we show that near-optimal performance can be obtained with a number of measurements that is roughly proportional to the number of bits used by the encoder. We end by briefly discussing these results in the context of image compression.

Recently, a series of exciting results have shown that it is possible to reconstruct a sparse signal exactly from a very limited number of linear measurements by solving a convex optimization program. If our underlying signal f can be written as a superposition of B elements from a known basis, it is possible to recover f from a projection onto a generic subspace of dimension about B log N. Moreover, the procedure is robust to measurement error; adding a perturbation of size ∈ to the measurements will not induce a recovery error of more than a small constant times ∈. In this paper, we will briefly overview these results, and show how the recovery via convex optimization can be implemented in an efficient manner, and present some numerical results illustrating the practicality of the procedure.

The wavelet transform provides a sparse representation for smooth images, enabling efficient approximation and compression using techniques such as zerotrees. Unfortunately, this sparsity does not extend to piecewise smooth images, where edge discontinuities separating smooth regions persist along smooth contours. This lack of sparsity hampers the efficiency of wavelet-based approximation and compression. On the class of images containing smooth C2 regions separated by edges along smooth C2 contours, for example, the asymptotic rate-distortion (R-D) performance of zerotree-based wavelet coding is limited to D(R) (< or = 1/R, well below the optimal rate of 1/R2. In this paper, we develop a geometric modeling framework for wavelets that addresses this shortcoming. The framework can be interpreted either as 1) an extension to the "zerotree model" for wavelet coefficients that explicitly accounts for edge structure at fine scales, or as 2) a new atomic representation that synthesizes images using a sparse combination of wavelets and wedgeprints--anisotropic atoms that are adapted to edge singularities. Our approach enables a new type of quadtree pruning for piecewise smooth images, using zerotrees in uniformly smooth regions and wedgeprints in regions containing geometry. Using this framework, we develop a prototype image coder that has near-optimal asymptotic R-D performance D(R) < or = (log R)2 /R2 for piecewise smooth C2/C2 images. In addition, we extend the algorithm to compress natural images, exploring the practical problems that arise and attaining promising results in terms of mean-square error and visual quality.

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.

Inherent to photograph-like images are two types of structures: large smooth regions and geometrically smooth edge contours separating those regions. Over the past years, efficient representations and algorithms have been developed that take advantage of each of these types of structure independently: quadtree models for 2D wavelets are well-suited for uniformly smooth images (C/sup 2/ everywhere), while quadtree-organized wedgelet approximations are appropriate for purely geometrical images (containing nothing but C/sup 2/ contours). This paper shows how to combine the wavelet and wedgelet representations in order to take advantage of both types of structure simultaneously. We show that the asymptotic approximation and rate-distortion performance of a wavelet-wedgelet representation on piecewise smooth images mirrors the performance of both wavelets (for uniformly smooth images) and wedgelets (for purely geometrical images). We also discuss an efficient algorithm for fitting the wavelet-wedgelet representation to an image; the convenient quadtree structure of the combined representation enables new algorithms such as the recent WSFQ geometric image coder.

Wavelet-based image coders optimally represent smooth regions and isolated point singularities. However, wavelet coders are less adept at representing perceptually important edge singularities, and coding performance suffers significantly as a result. We propose a novel two-stage image coder framework based on modeling images as edge cartoons + textures. In stage 1, we infer and efficiently code the edge information from the image using a multiscale wedgelet decomposition. In stage 2, we code the residual, "edgeless" texture image using a standard wavelet coder. Our preliminary coder improves significantly over standard wavelet coding techniques in terms of visual quality.

The most perceptually important features in images are geometrical, the most prevalent being the smooth contours ("edges") that separate different homogeneous regions and delineate distinct objects. Although wavelet based algorithms have enjoyed success in many areas of image processing, they have significant shortcomings in their treatment of edges. Wavelets do not parsimoniously capture even the simplest geometrical structure in images, and as a result wavelet based processing algorithms often produce images with ringing around the edges. The multiscale wedgelet framework is a first step towards explicitly capturing geometrical structure in images. The framework has two components: decomposition and representation. The multiscale wavelet decomposition divides the image into dyadic blocks at different scales and projects these image blocks onto wedgelets - simple piecewise constant functions with linear discontinuities. The multiscale wedgelet representation is an approximation of the image built out of wedgelets from the decomposition. In choosing the wedgelets to form the representation, we can weigh several factors: the error between the representation and the original image, the parsimony of the representation, and whether the wedgelets in the representation form "natural" geometrical structure. We show that an efficient multiscale wedgelet decomposition is possible if we carefully choose the set of possible wedgelet orientations. We also present a modeling framework that makes it possible to incorporate simple geometrical constraints into the choice of wedgelet representation, resulting in parsimonious image approximations with smooth contours.

Most wavelet-based image coders fail to model the joint coherent behavior of wavelet coefficients near edges. Wedgelets offer a convenient parameterization for the edges in an image, but they have yet to yield a viable compression algorithm. In this paper, we propose an extension of the zerotree-based space-frequency quantization (SFQ) algorithm by adding a wedgelet symbol to its tree-pruning optimization. This incorporates wedgelets into a rate-distortion compression framework and allows simple, coherent descriptions of the wavelet coefficients near edges. The resulting method yields improved visual quality and increased compression efficiency over the standard SFQ technique.

Wavelet domain algorithms have risen to the forefront of image processing. The power of these algorithms is derived from the fact that the wavelet transform restructures images in a way that makes statistical modeling simpler. Since edge singularities account for the most important information in images, understanding how edges behave in the wavelet domain is the key to modeling. In the past, wavelet-domain statistical models have codified the tendency for wavelet coefficients representing an edge to be large across scale. We use the complex wavelet transform to uncover the phase behavior of wavelet coefficients representing an edge. This allows us to design a hidden Markov tree model that can discriminate between large magnitude wavelet coefficients caused by texture regions and ones caused by edges.

Wavelet-domain hidden Markov models have proven to be useful tools for statistical signal and image processing. The hidden Markov tree (HMT) model captures the key features of the joint probability density of the wavelet coefficients of real-world data. One potential drawback to the HMT framework is the need for computationally expensive iterative training to fit an HMT model to a given data set (e.g., using the expectation-maximization algorithm). We greatly simplify the HMT model by exploiting the inherent self-similarity of real-world images. The simplified model specifies the HMT parameters with just nine meta-parameters (independent of the size of the image and the number of wavelet scales). We also introduce a Bayesian universal HMT (uHMT) that fixes these nine parameters. The uHMT requires no training of any kind, while extremely simple, we show using a series of image estimation/denoising experiments that these new models retain nearly all of the key image structure modeled by the full HMT. Finally, we propose a fast shift-invariant HMT estimation algorithm that outperforms other wavelet-based estimators in the current literature, both visually and in mean square error.

Multiresolution signal and image models such as the hidden Markov tree aim to capture the statistical structure of smooth and singular (edgy) regions. Unfortunately, models based on the orthogonal wavelet transform suffer from shift-variance, making them less accurate and realistic. We extend the HMT modeling framework to the complex wavelet transform, which features near shift-invariance and improved angular resolution compared to the standard wavelet transform. The model is computationally efficient (with linear-time computation and processing algorithms) and applicable to general Bayesian inference problems as a prior density for the data. In a simple estimation experiment, the complex wavelet HMT model outperforms a number of high-performance denoising algorithms, including redundant wavelet thresholding (cycle spinning) and the redundant HMT.

Multiresolution signal and image models such as the hidden Markov tree (HMT) aim to capture the statistical structures of smooth and singular (textured and edgy) regions. Unfortunately, models based on the orthogonal wavelet transform suffer from shift-variance, making them less accurate and realistic. We extend the HMT modeling framework to the complex wavelet transform, which features near shift-invariance and improved angular resolution compared to the standard wavelet transform. The model is computationally efficient (featuring linear-time computation and processing algorithms) and applicable to general Bayesian inference problems as a prior density for the data. We develop a simple multiscale maximum likelihood classification scheme based on the complex wavelet HMT that outperforms methods based on real-valued wavelet HMTs. The resulting classifier can be used as a front end in a more sophisticated multiscale segmentation algorithm.

Wavelet-domain hidden Markov models have proven to be useful tools for statistical signal and image processing. The hidden Markov tree (HMT) model captures the key features of the joint statistics of the wavelet coefficients of real-world data. One potential drawback to the HMT framework is the need for computationally expensive iterative training (using the EM algorithm, for example). In this paper, we propose two reduced-parameter HMT models that capture the general structure of a broad class of grayscale images. The image HMT (iHMT) model leverages the fact that for a large class of images the structure of the HMT is self-similar across scale. This allows us to reduce the complexity of the iHMT to just nine easily trained parameters (independent of the size of the image and the number of wavelet scales). In the universal HMT (uHMT) we take a Bayesian approach and fix these nine parameters. The uHMT requires no training of any kind. While simple, we show using a series of image estimation/denoising experiments that these two new models retain nearly all of the key structures modeled by the full HMT. Based on these new models, we develop a shift-invariant wavelet denoising scheme that outperforms all algorithms in the current literature.