Multiscale Processing for Image Manifolds
M. Wakin H. Choi R. Baraniuk D. Donoho

Our aim is to analyze and better understand the geometric structure relating one image to another and to use this insight to develop novel image processing tools, representations, and algorithms. We begin with carefully restricted classes of images generated by varying the underlying articulation parameters of an object (pose, attitude, light source position, and so on). These images can be viewed as points on a low-dimensional imaging parameter articulation manifold (IPAM) in the high-dimensional ambient space. We have developed theory and methods for the inverse problem of estimating, from a given image on or near an IPAM, the underlying parameters that produced it. Our approach is centered on the observation that, while typical image manifolds are not differentiable, they have an intrinsic multiscale geometric structure. In fact, each IPAM has a family of approximate tangent spaces, each one good at a certain resolution. Putting this structural aspect to work, we have developed a new algorithm for high-accuracy parameter estimation based on a coarse-to-fine Newton iteration through the family of approximate tangent spaces.
Paper: ICASSP 2005 , Wavelets XI 2005

Directional Hypercomplex Wavelets for Multidimensional Signal Analysis and Processing
W. Chan, H. Choi, R. Baraniuk

We extend the wavelet transform to handle multi-dimensional signals that are smooth save for singularities along lower-dimensional manifolds. We first generalize the complex wavelet transform to higher dimensions using a multi-dimensional Hilbert transform. Then, using the resulting hypercomplex wavelet transform (HWT) as a building block, we construct new classes of nearly shift-invariant wavelet frames that are oriented along lower-dimensional subspaces. The HWT can be computed efficiently using a 1-D dual-tree complex wavelet transform along each signal axis. We demonstrate how the HWT can be used for fast line detection in 3-D. (ICASSP 2004: paper)

Multiscale Geometry Tilings and Models
M. Wakin, J. Romberg, V. Chandrasekaran, D. Baron, R. Baraniuk

Geometric tilings provide an alternative framework for approximation and compression of piecewise constant functions containing smooth discontinuities. Unlike additive wavelet-based techniques, tilings use exactly one atom at each location in the data. In 2D, wedgelets provide piecewise linear approximations to edges (and perform optimally for C² edges: VCIP 2003 paper). In higher dimensions, we have introduced surflets which provide piecewise polynomial approximations to arbitrary C^K discontinuities (CISS 2004 paper). We have developed multiscale statistical models for these tilings and have introduced compression algorithms with optimal rate-distortion performance. These concepts are extended to our work with wedgeprints and complex wavelets (see below).

Wedgeprints for Piecewise Smooth Image Compression
M. Wakin, J. Romberg, H. Choi, R. Baraniuk

We use wedgelets to develop a tree-structured representation for wavelet coefficients in geometric regions. Our wedgeprint representation is the result of projecting a local wedgelet decomposition to the wavelet domain. Like a zerotree, a wedgeprint explicitly describes an entire subtree of wavelet coefficients using few bits; wedgeprints do so in the high-energy regions near edges, however, and implicitly model the coherency among geometric wavelet coefficients. We develop an image compression algorithm combining wedgeprints (for geometric regions) with zerotrees (for smooth regions) into a single top-down wavelet coder. This coder achieves near-optimal rate-distortion performance for certain piecewise smooth images (ICIP 2003 paper) and allows a discrete implementation that outperforms most state-of-the-art image coders in terms of visual quality and mean-square error (Wavelets X 2003 paper).

3-D Mesh Geometry Modeling
S. Lavu, H. Choi, M. Jansen, R. Baraniuk

3-Dimensional (3-D) surfaces are used in applications such as animations, 3-D object modeling and visualization. The geometries of such surfaces are often approximated using very large complex polygonal meshes. We are developing 3-D geometry compression algorithms based on normal meshes and mesh wavelet transforms. We have developed an Estimation-Quantization based algorithm to compress 3-D normal meshes (DCC 2003 paper: PDF, Masters thesis: PDF). We are also extending normal mesh based algorithms to 2-D image case and have some promising results (ICIP 2001 paper: PDF & PS, ).

More: normal meshes for 3-D geometry, normal meshes for 2-D images

ForWaRD: Fourier-Wavelet Regularized Deconvolution
R. Neelamani (Neelsh), H. Choi, R. Baraniuk

Fourier-Wavelet Regularized Deconvolution (ForWaRD) is an efficient, hybrid algorithm that performs deblurring using both the Fourier and wavelet domain processing. The Fourier processing exploits the Fourier transform's sparse representation of the colored noise inherent in deconvolution, while the wavelet processing exploits the wavelet domain's sparse representation of piecewise smooth signals and images. ForWaRD is applicable to all ill-conditioned deconvolution problems, and its estimate features minimal ringing. For certain classes of deconvolution problems, ForWaRD's MSE decays with the optimal rate as the number of samples increases.
Paper: IEEE Trans. SP, 2004.
Software: Matlab code.

JPEG Compression History Estimation for Color Images
R. Neelamani (Neelsh), R. de Queiroz, Zhigang Fan (Xerox), Sanjeeb Dash (IBM), R. Baraniuk

We routinely encounter digital color images that were previously JPEG-compressed. Enroute to the image's current representation, the previous JPEG compression's various settings---termed its JPEG compression history (CH)--are often discarded after the JPEG decompression step. Given a JPEG-decompressed color image, we want to estimate its lost JPEG CH. Our key insight is that the previous JPEG compression's quantization step introduces a lattice structure in the discrete cosine transform domain. We have designed two approaches that exploit this structure to solve the JPEG Compression History Estimation (CHEst) problem. Both approaches provide robust JPEG CHEst performance in practice. Simulations demonstrate that JPEG CHEst can be extremely useful in JPEG recompression; the estimated CH allows us to recompress a JPEG-decompressed image with minimal distortion (large signal-to-noise-ratio) and simultaneously achieve a small file-size.
Papers: IEEE Trans. IP, 2006, SIAM J. Discrete Math. (submitted).
Software: Matlab code.

Distributed Multiscale Signal Processing for Sensor Networks
R. Wagner, V. Delouille, H. Choi, R. Baraniuk

Applying wavelet techniques to sensor networks poses a twofold challenge. First, wavelet transforms typically operate on data in a centralized setting, with access to the entire dataset. Such omniscience is not feasible for transforms within a sensor network, where sensors can only share data efficiently in regions defined by the networking protocol at work in the sensornet. Data flow between sensors must be minimized and aligned to preferred networking flows. Second, the bulk of wavelet theory applies to data sampled on a regular grid, a restriction to which any realistic placement of sensors will not typically conform.

To this end, we are working to develop efficient, implementable multiscale wavelet analysis tools for sensor networks. The first such transform ( ICASSP 2005 ) integrates seemlessly with multiscale routing structures in a sensor network, fitting piecewise-constant measurement approximations over clusters defined by the routing protocol. The second ( SSP 2005 ) is based on the theory of wavelet lifting and requires no a priori multiscale structure in the network. Instead, it builds a series of distributed meshes which enable distributed computation of the filters used in each lifting stage. Currently, we are working to develop protocols for distributed compression, de-noising, and query processing using transform data, and we exploring real-world implementation issues such as packet loss, loss of encoder/decoder synchronization, and coefficient quantization effects. We are also investigating extension of the transform to irregularly sampled three-dimensional grids.

Robust Distributed Estimation in Sensor Networks
V. Delouille, R. Neelamani, V. Chandrasekaran, R. Baraniuk

Sensors, signal processing, and wireless communication technologies have matured to the point where large networks of sensor nodes can now be easily deployed in a wide variety of environments, making them very attractive for large-scale applications like environmental monitoring, security surveillance, and disaster relief. Often battery-powered, sensor nodes are capable of sensing, computing, and communicating information. We are developing distributed estimation algorithms that replace global communication and centralized computation by parallel, local communication and computation, effectively distributing the matrix inverse computation involved in a Wiener or Kalman filter across the network.

Our distributed embedded polygons algorithm for distributed linear minimum mean-squared-error estimation is local, fast to converge, and resilient to communication failures caused by sleeping sensors and faulty transmissions. Simulation studies indicate that energy consumption for iterative estimation increases substantially as more links fail or nodes sleep. Thus, somewhat surprisingly, energy conservation strategies such as low-powered transmission and aggressive sleep schedules could actually be counterproductive.
Papers: IEEE Trans. SP, 2006, IPSN 2004, SSP 2003.
Software: Matlab code.

Optimal Sampling Strategies for Multiscale Processes
V. Ribeiro, R. Riedi, R. Baraniuk

We design strategies to optimally sample multiscale stochastic processes in order to estimate their global average optimally. This has implications for Internet measurement, sensor network design, environmental monitoring, etc. A multiscale process consists of a set of univariate random variables that are organized like the nodes of a tree. Nodes at the bottom are called leaves and the topmost node is the root. We associate each node with the average of a physical process over some region with nodes at higher scales corresponding to larger regions. The root thus represents the global average of the process and the leaves represent local samples. The question we address is: Among all possible sets of leaves of size n, which set gives the best linear estimate of the root in terms of minimum mean squared error?
Paper: 2nd Erich Lehmann Symposium

pathChirp: Efficient available bandwidth estimation for network paths
V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell

Knowledge of the available or unused bandwidth on a network path can be crucial for optimizing network performance. pathChirp is a new active probing tool for estimating the available bandwidth on a communication network path. Based on the concept of self-induced congestion, pathChirp features an exponential flight pattern of probes we call a chirp. Packet chirps offer several significant advantages over current probing schemes based on packet pairs or packet trains. By rapidly increasing the probing rate within each chirp, pathChirp obtains a rich set of information from which to dynamically estimate the available bandwidth.
Paper: Passive and Active Measurement Workshop 2003

STAB: Locating available bandwidth bottlenecks
V. Ribeiro, R. Riedi, R. Baraniuk

The Spatio-Temporal Available Bandwidth estimator (STAB) is a new probing tool that locates thin links - links with less available bandwidth than those preceding them on a path. By localizing thin links, STAB facilitates network operations and troubleshooting, provides insight into what causes network congestion, and aids network-aware applications such as grid computing. The tool combines the concept of "self-induced congestion", the probing technique of "packet tailgating", and special probing trains called "chirps" to efficiently locate the thin links.
Paper: IEEE Internet Computing

A Multifractal Wavelet Model with Application to TCP Network Traffic
R. Riedi, M.S. Crouse, V. Ribeiro, R. Baraniuk

Traffic models that capture important features of observed Internet traffic provide synthetic data for simulation purposes as well as give key insights into the causes of the dynamics in traffic. We develop a new multiscale modeling framework for characterizing positive-valued data with long-range-dependent correlations (1/f noise) such as network traffic. Using the Haar wavelet transform and a special multiplicative structure on the wavelet and scaling coefficients to ensure positive results, the model provides a rapid O(N) cascade algorithm for synthesizing N-point data sets. We derive a scheme for matching the model to real data observations and, to demonstrate its effectiveness, apply the model to network traffic synthesis.
Paper: IEEE Transactions on Information Theory

Multiscale Queuing Analysis of Long-Range-Dependent Network Traffic
V. Ribeiro, R. Riedi, M.S. Crouse, R. Baraniuk

Many studies have indicated the importance of capturing scaling properties when modeling traffic loads; however, the influence of long-range dependence (LRD) and marginal statistics still remains on unsure footing. We study these two issues using a novel multiscale approach to queuing analysis. The queuing analysis provides a simple closed form approximation to the tail queue probability, valid for any traffic model and any given buffer size. Our results clearly indicate that the marginal distribution of traffic at different time-resolutions affects queuing and that a Gaussian assumption can lead to over-optimistic predictions of tail queue probability even when taking LRD into account.
Paper: INFOCOM 2000.

Connection-Level Analysis and Modeling of Network Traffic
S. Sarvotham, R. Riedi, R. Baraniuk

We develop a framework for analyzing and modeling network traffic that incorporates connection-level information. A careful study of many traffic traces acquired in different networking situations reveals that traffic bursts typically arise from just a few high-volume connections that dominate all others. We term such dominating connections as Alpha connections. Alpha traffic is caused by large file transmissions over high bandwidth links and is extremely bursty (non-Gaussian). Stripping the Alpha traffic from an aggregate trace leaves a Beta traffic residual that is Gaussian and shares the same fractal scaling exponent as the aggregate traffic. Beta traffic is caused by both small and large file transmissions over low bandwidth links. The Alpha/Beta traffic analysis reveals the influence of user-behavior and the network conditions on the aggregate traffic.
Paper: IMW 2001, Computer Networks Journal.

Crosstalk Mitigation
N. Ahmed, R. Gaikwad, R. Baraniuk

Digital Subscriber Line (DSL) techniques provide high-speed broadband access over ordinary twisted pair telephone wires by extending the range of usable frequency. Ordinary voice calls use a bandwidth of up to 4Khz while with DSL the range of usable frequencies is extended to several Mhz. Typically twisted pair wires carrying service from the central office (CO) to remote terminals (RTs) are packed closely togther, up to 50 at a time, within cable binders. The proximity of these wires lead to electromagnetic coupling, or energy leaking from one wire pair to others, which often increases with frequency. Crosstalk severely limits the achievable data rates of existing DSL systems and as market penetration increases, the problem will only get larger. We provide several crosstalk mitigation strategies that significantly improve the communications performance of DSL systems. The first uses spectral shaping at the CO to jointly optimize the transmit spectra of all the users of a particular DSL service. The second is a receiver side blind crosstalk cancellation technique which requires no coordination amongst users.

Related publications: ETTC 2002: paper, Globecom 2001: paper, ICC 1999: paper, CISS 1999: paper.

Throughput Maximization
N. Ahmed, R. Baraniuk

Fading channels provide a particulary hostile environment for reliable communications. In such channels the transmitted signal is scattered in a time-vary manner resulting in random fluctuations of the received power level. Transmitters map data to codewords prior to transmission to combat this effect. Historically, rigorous analysis of fading channels is performed from the perspective that each codeword is only transmitted once. This approach works well when transmitters have infinite coding delay and use infinite-length codewords. When this occurs it is possible to transmit reliably at ergodic capacity.

Practical systems are delay-limited and must use finite-length codewords. Single-attempt measures, outage-capacity and delay-limited capacity, are conventionally used to quantify the performance of delay-limited systems. However, both measures have shortcomings. Outage-capacity is not a measure of error-free communications, while delay-limited capacity is an overly conservative estimate of performance. In practice, multiple transmission attempts per codeword can be used to ensure reliable delivery of data. When analyzed from this perspective, multi-attempt measures show that it is possible to achieve a communications throughput much higher than that predicted by conventional single-attempt measures.

Related publications: Allerton 2003: paper, Globecom 2004: paper submitted.

Neyman-Pearson Learning with Support Vector Machines
Mark Davenport Clay Scott Richard Baraniuk

The support vector machine (SVM) is one of the most powerful and widely applied methods for learning a classifier from training data. SVMs attempt to learn a decision rule that minimizes the probability of incorrectly classifying a pattern. For some applications, such as anomaly detection, the probability of error is not the most appropriate criterion. The Neyman-Pearson (NP) approach seeks instead to minimize false negatives while constraining false positives to be below a certain significance level. The theory of learning classifiers with respect to the NP criterion has recently begun to emerge and there is now a need for the development of practical algorithms. We are looking at adapting the SVM approach to the NP framework, from both a theoretical and algorithmic perspective.

A Theory of Information Processing

Electrical signals can carry two "things": power and information. Signal processing theory concerns the structure of the signals (it does not describe what they represent nor how well they represent it) and frames how systems affect signal components (not how the system's actions affect what it conveys). Understanding power formed the basis of electrical engineering, and is well understood; understanding information representation and processing is far from complete. Shannon's work describes how to efficiently represent signals (whether they represent information or not) and how communication channels can reliably communicate digital signals. Our work considers the information rather than the signal, and we have quantified how well a signal codes information and how systems affect the information conveyed by their inputs.

Neural Information Processing

In the nervous system, sensory information is represented in single neurons by sequences of action potentials--brief, isolated pulses having identical waveforms--occurring randomly in time. These signals are usually modeled as point processes; however, these point processes have a dependence structure and, because of the presence of a stimulus, are non-stationary. Thus, sophisticated non-Gaussian signal processing techniques are needed to analyze data recorded from sensory neurons to determine what aspects of the stimulus are being emphasized and how emphatic that representation might be. A recent paper analyzes well-established data analysis techniques for single-neuron discharge patterns. Another recent paper describes how we applied our theory of information processing to neural coding.