Readout multiplexing is a promising solution to overcome hardware limitations and data bottlenecks in imaging with single-photon detectors. Conventional multiplexed readout processing creates an upper bound on photon counts at a very fine time scale, where frames with multiple detected photons must either be discarded or allowed to introduce significant bias. We formulate multiphoton coincidence resolution as an inverse imaging problem and introduce a solution framework to probabilistically resolve the spatial locations of photon incidences. Specifically, we develop a theoretical abstraction of row–column multiplexing and a model of photon events that make readouts ambiguous. Using this, we propose a novel estimator that spatially resolves up to four coincident photons. Monte Carlo simulations show that our proposed method increases the peak signal-to-noise ratio (PSNR) of reconstruction by 3 to 4 dB compared to conventional methods under optimal incident flux conditions. Additionally, this method reduces the required number of readout frames to achieve the same mean-squared error as other methods by a factor of ~ 4. Finally, our method matches the Cramér–Rao bound for detection probability estimation for a wider range of incident flux values compared to conventional methods. While demonstrated for a specific detector type and readout architecture, this method can be extended to more general multiplexing with different detector models.

Conventional wisdom suggests that single-photon lidar (SPL) should operate in low-light conditions to minimize dead-time effects. Many methods have been developed to mitigate these effects in synchronous SPL systems. However, solutions for free-running SPL remain limited despite the advantage of reduced histogram distortion from dead times. To improve the accuracy of free-running SPL, we propose a computationally efficient joint maximum likelihood estimator of the signal flux, the background flux, and the depth using only histograms, along with a complementary regularization framework that incorporates a learned point cloud score model as a prior. Simulations and experiments demonstrate that free-running SPL yields lower estimation errors than its synchronous counterpart under identical conditions, with our regularization further improving accuracy.

Passive hyperspectral longwave infrared measurements are remarkably informative about the surroundings. Remote object material and temperature determine the spectrum of thermal radiance, and range, air temperature, and gas concentrations determine how this spectrum is modified by propagation to the sensor. We introduce a passive range imaging method based on computationally separating these phenomena. Previous methods assume hot and highly emitting objects; ranging is more challenging when objects' temperatures do not deviate greatly from air temperature. Our method jointly estimates range and intrinsic object properties, with explicit consideration of air emission, though reflected light is assumed negligible. Inversion being underdetermined is mitigated by using a parametric model of atmospheric absorption and regularizing for smooth emissivity estimates. To assess where our estimate is likely accurate, we introduce a technique to detect which scene pixels are significantly influenced by reflected downwelling. Monte Carlo simulations demonstrate the importance of regularization, temperature differentials, and availability of many spectral bands. We apply our method to longwave infrared (8-13 $\mathrm{\mu }\mathrm{m}$μm) hyperspectral image data acquired from natural scenes with no active illumination. Range features from 15 m to 150 m are recovered, with good qualitative match to lidar data for pixels classified as having negligible reflected downwelling.

In a built environment, wanting to see without direct line of sight is often due to being outside a doorway. The two vertical edges of the doorway provide occlusions that can be exploited for non-line-of-sight imaging by forming corner cameras. While each corner camera can separately yield a robust 1D reconstruction, joint processing suggests novelties in both forward modeling and inversion. The resulting doorway camera provides accurate and robust 2D reconstructions of the hidden scene. This work provides a novel inversion algorithm to jointly estimate two views of change in the hidden scene, using the temporal difference between photographs acquired on the visible side of the doorway. Successful reconstruction is demonstrated in a variety of real and rendered scenarios, including different hidden scenes and lighting conditions. A Cramer-Rao bound analysis is used to demonstrate the 2D resolving power of the doorway camera over other passive acquisition strategies and to motivate the novel biangular reconstruction grid.

Non-line-of-sight (NLOS) imaging is a rapidly advancing technology that provides asymmetric vision: seeing without being seen. Though limited in accuracy, resolution, and depth recovery compared to active methods, the capabilities of passive methods are especially surprising because they typically use only a single, inexpensive digital camera. One of the largest challenges in passive NLOS imaging is ambient background light, which limits the dynamic range of the measurement while carrying no useful information about the hidden part of the scene. In this work we propose a new reconstruction approach that uses an optimized linear transformation to balance the rejection of uninformative light with the retention of informative light, resulting in fast (video-rate) reconstructions of hidden scenes from photographs of a blank wall under high ambient light conditions.

Edge-resolved transient imaging (ERTI) is a method for non-line-of-sight imaging that combines the use of direct time of flight for measuring distances with the azimuthal angular resolution afforded by a vertical edge occluder. Recently conceived and demonstrated for the first time, no performance analyses or optimizations of ERTI have appeared in published papers. This paper explains how the difficulty of detection of hidden scene objects with ERTI depends on a variety of parameters, including illumination power, acquisition time, ambient light, visible-side reflectivity, hidden-side reflectivity, target range, and target azimuthal angular position. Based on this analysis, optimization of the acquisition process is introduced whereby the illumination dwell times are varied to counteract decreasing signal-to-noise ratio at deeper angles into the hidden volume. Inaccuracy caused by a coaxial approximation is also analyzed and simulated.

Variations in the intensity of the incident beam can cause significant inaccuracies in microscopes that use focused beams of electrons or ions. Existing mitigation methods depend on the artifacts having characteristic spatial structures explained by the raster scan pattern and temporal correlation of the beam current variations. We show that recently introduced time-resolved measurement methods create robustness to beam current variations that improve significantly upon existing methods while not depending on separability of artifact structure from underlying image content. These advantages are illustrated through Monte Carlo simulations representative of both helium ion microscopy (higher secondary electron yield) and scanning electron microscopy (lower secondary electron yield). Notably, this demonstrates that when the beam current variation is appreciable, time-resolved measurements provide a novel benefit in particle beam microscopy that extends to low secondary electron yields.

We demonstrate non-line-of-sight imaging of multi-depth scenes using only a single photograph from an ordinary digital camera. The hidden scene, comprising two images at different depths, is partially occluded from a visible wall by an opaque occluding object. The distance from the visible wall to the hidden surfaces, and the images they contain, are recovered.

Time-correlated single photon counting (TCSPC) is a powerful technique for lidar depth imaging, allowing for accurate range measurements from very low light levels. However, single-photon detectors used in TCSPC have a dead time after each photon detection, which blocks registration of subsequent photons arriving within that dead time, causing a distortion of the detection time distribution. The most common approach to avoiding dead time distortion is to optically reduce the photon arrival rate such that with high probability no photons arrive during the dead time. However, this prevents the high photon flux acquisition necessary for real-time applications such as autonomous navigation. In this paper, we propose a dead time compensation method that enables fast data acquisition with dead time-limited detectors. Specifically, we model dead time-affected detection times as a Markov chain, present a simple method for approximating the stationary distribution, and estimate depths using a log-matched filter matched to that distribution. Our method applies to multimodal imaging systems where a standard camera is used in conjunction with lidar to provide information about scene reflectivity. Simulation results for real 3D scenes show that our method reduces the root mean squared error by several orders of magnitude for the same acquisition time.

The ability to image scenery outside a camera's line-of-sight would be useful in a variety of applications, including autonomous vehicle collision avoidance, or for first responders to anticipate danger around a corner. When a wall obstructs the camera, light cast onto the floor from behind the wall may be used to recover angular variation of light intensity reflected by the hidden scene, forming a 1D scene projection. Recent work has demonstrated that temporal variation in a video, or sequence of floor images, may be used to image moving components of the hidden scene. However, in many applications, it would be useful to be able to image stationary components as well. This earlier approach was also designed for, and tested on, floors that have approximately uniform albedo, while many real floors have spatially varying albedo patterns such as checkered tiles and patterned carpets. In this work, we propose a method to reconstruct a 1D projection of all components in a hidden scene from a single photograph of the floor without assuming uniform floor albedo. Specifically, we derive a forward model that describes the measured photograph as a nonlinear combination of the unknown floor albedo and the light from behind the wall. The inverse problem, which is the joint estimation of floor albedo and a 1D reconstruction of the hidden scene, is then solved via optimization, where we introduce regularizers that help separate light variations in the measured photograph due to floor pattern and hidden scene, respectively. We demonstrate the effectiveness of our formulation and algorithm using synthetic and experimentally measured data.

We address the problem of estimating the parameter of a Bernoulli process. This arises in many applications, including photon-efficient active imaging where each illumination period is regarded as a single Bernoulli trial. We introduce a framework within which to minimize the mean-squared error (MSE) subject to an upper bound on the mean number of trials. This optimization has several simple and intuitive properties when the Bernoulli parameter has a beta prior. In addition, by exploiting typical spatial correlation using total variation regularization, we extend the developed framework to a rectangular array of Bernoulli processes representing the pixels in a natural scene. In simulations inspired by realistic active imaging scenarios, we demonstrate a 4.26 dB reduction in MSE due to the adaptive acquisition, as an average over many independent experiments and invariant to a factor of 3.4 variation in trial budget.

We demonstrate that human decision-making agents do social learning whether it is beneficial or not. Specifically, we consider binary Bayesian hypothesis testing with multiple agents voting sequentially for a team decision, where each one observes earlier-acting agents' votes as well as a conditionally independent and identically distributed private signal. While the best strategy (for the team objective) is to ignore the votes of earlier-acting agents, human agents instead tend to be affected by others' decisions. Furthermore, they are almost equally affected in the team setting as when they are incentivized only for individual correctness. These results suggest that votes of earlier-acting agents should be withheld (not shared as public signals) to improve team decision-making performance; humans are insufficiently rational to innately apply the optimal decision rules that would ignore the public signals.

Using detector arrays can speed up lidar systems by parallelizing acquisition. However, current SPAD arrays have time bins longer than typical laser pulse durations, resulting in measurement errors dominated by quantization. We propose an optical time-of-flight system that uses subtractive dither to improve image depth resolution. Modeling the measurement noise with a generalized Gaussian distribution further improves estimation error in simulations, although model mismatch prevents the same advantage for our experimental data. Experimental results with the ratio of laser pulse standard deviation to quantization bin duration equal to 0.15 and using an average of 267 photons per pixel show a reduction in RMS error as large as 9-fold over estimates from coarsely quantized data.

Depth profile reconstruction of a scene at low light levels using an active imaging setup has wide-ranging applications in remote sensing. In such low-light imaging scenarios, single-photon detectors are employed to time-resolve individual photon detections. However, even with single-photon detectors, current frameworks are limited to using hundreds of photon detections at each pixel to mitigate Poisson noise inherent in light detection. In this paper, we discuss two pixelwise imaging frameworks that allow accurate reconstruction of depth profiles using small numbers of photon detections. The first framework addresses the problem of depth reconstruction of an opaque target, in which it is assumed that each pixel contains exactly one reflector. The second framework addresses the problem of reconstructing multiple-depth pixels. In each scenario, our framework achieves photon efficiency by combining accurate statistics for individual photon detections with a longitudinal sparsity constraint tailored to the imaging problem. We demonstrate the photon efficiencies of our frameworks by comparing them with conventional imagers that use more naïve models based on high light-level assumptions.

A single-pixel camera is able to computationally form spatially resolved images using one photodetector and a spatial light modulator. The images it produces in low-light-level operation are imperfect, even when the number of measurements exceeds the number of pixels, because its photodetection measurements are corrupted by Poisson noise. Conventional performance analysis for single-pixel imaging generates estimates of mean-square error (MSE) from Monte Carlo simulations, which require long computational times. In this letter, we use random matrix theory to develop a closed-form approximation to the MSE of the widely used least-squares inversion method for Poisson noise-limited single-pixel imaging. We present numerical experiments that validate our approximation and a motivating example showing how our framework can be used to answer practical optical design questions for a single-pixel camera.

In software-as-a-service applications provisioned through cloud computing, locally cached data are often modified with updates from new versions. In some cases, with each edit, one may want to preserve both the original and new versions. In this paper, we focus on cases in which only the latest version must be preserved. Furthermore, it is desirable for the data to not only be compressed but to also be easily modified during updates, since representing information and modifying the representation both incur cost. We examine whether it is possible to have both compression efficiency and ease of alteration, in order to promote codeword reuse. In other words, we study the feasibility of a malleable and efficient coding scheme. The tradeoff between compression efficiency and malleability cost-the difficulty of synchronizing compressed versions-is measured as the length of a reused prefix portion. The region of achievable rates and malleability is found. Drawing from prior work on common information problems, we show that efficient data compression may not be the best engineering design principle when storing software-as-a-service data. In the general case, goals of efficiency and malleability are fundamentally in conflict.

Light detection and ranging systems reconstruct scene depth from time-of-flight measurements. For low light-level depth imaging applications, such as remote sensing and robot vision, these systems use single-photon detectors that resolve individual photon arrivals. Even so, they must detect a large number of photons to mitigate Poisson shot noise and reject anomalous photon detections from background light. We introduce a novel framework for accurate depth imaging using a small number of detected photons in the presence of an unknown amount of background light that may vary spatially. It employs a Poisson observation model for the photon detections plus a union-of-subspaces constraint on the discrete-time flux from the scene at any single pixel. Together, they enable a greedy signal-pursuit algorithm to rapidly and simultaneously converge on accurate estimates of scene depth and background flux, without any assumptions on spatial correlations of the depth or background flux. Using experimental single-photon data, we demonstrate that our proposed framework recovers depth features with 1.7 cm absolute error, using 15 photons per image pixel and an illumination pulse with 6.7-cm scaled root-mean-square length. We also show that our framework outperforms the conventional pixelwise log-matched filtering, which is a computationally-efficient approximation to the maximum-likelihood solution, by a factor of 6.1 in absolute depth error.

Capturing depth and reflectivity images at low light levels from active illumination of a scene has wide-ranging applications. Conventionally, even with single-photon detectors, hundreds of photon detections are needed at each pixel to mitigate Poisson noise. We introduce a robust method for estimating depth and reflectivity using on the order of 1 detected photon per pixel averaged over the scene. Our computational imager combines physically accurate single-photon counting statistics with exploitation of the spatial correlations present in real-world reflectivity and 3D structure. Experiments conducted in the presence of strong background light demonstrate that our computational imager is able to accurately recover scene depth and reflectivity, while traditional maximum likelihood-based imaging methods lead to estimates that are highly noisy. Our framework increases photon efficiency 100-fold over traditional processing and thus will be useful for rapid, low-power, and noise-tolerant active optical imaging.

We show that social learning is not useful in a model of team binary decision making by voting, where each vote carries equal weight. Specifically, we consider Bayesian binary hypothesis testing where agents have any conditionally-independent observation distribution and their local decisions are fused by any L-out-of-N fusion rule. The agents make local decisions sequentially, with each allowed to use its own private signal and all precedent local decisions. Though social learning generally occurs in that precedent local decisions affect an agent's belief, optimal team performance is obtained when all precedent local decisions are ignored. Thus, social learning is futile, and secret ballots are optimal. This conclusion contrasts with typical studies of social learning because we include a fusion center rather than concentrating on the performance of the latest-acting agents.

Multiplexed imaging is a powerful mechanism for achieving high signal-to-noise ratio (SNR) in the presence of signal-independent additive noise. However, for imaging in presence of only signal-dependent shot noise, multiplexing has been shown to significantly degrade SNR. Hence, multiplexing to increase SNR in presence of Poisson noise is normally thought to be infeasible. In this paper, we present an exception to this view by demonstrating multiplexing advantage when the scene parameters are non-negative valued and are observed through a low-rate Poisson channel.

We present a new method for simultaneously denoising and unwrapping phase in multi-frequency homodyne time-of-flight ranging for the formation of accurate depth maps despite low SNR of raw measurements. This is achieved with a new generalized approximate message passing (GAMP) algorithm for minimum mean-squared error estimation of the phase. A detailed, physically-accurate acquisition model is central in achieving high accuracy, and the use of the GAMP methodology allows low computational complexity despite dense dependencies and the nonlinearity and non-Gaussianity of the acquisition model. Numerical simulations demonstrate that our integrated approach performs better than separate unwrapping followed by denoising. This performance translates to lowering the optical power consumption of time-of-flight cameras for a fixed acquisition quality.

Range estimation at low light-levels is accomplished using pulsed illumination of the target and time-of-flight measurement of backscattered light using single-photon detectors. Photon arrival statistics for this problem are time-inhomogeneous Poisson point processes where the rate function is determined by the illumination waveform. Given the flexibility to choose from different illumination waveforms, an important design question is - how does the range estimation performance depend on the pulse shape? The maximum-likelihood (ML) range estimation problem is nonlinear and thus it is difficult to analytically compare the estimation performance from different illumination waveforms. In this paper, we present an information-theoretic framework for evaluating ML range estimation performance. We derive relationships between the entropy of the photon arrival observations and the Cramér-Rao lower bound (CRLB) on the range estimate by extending De Brujin's identity and isoperimetric properties for non-Gaussian distributions.

We consider sequential Bayesian binary hypothesis testing where each individual agent makes a binary decision motivated only by minimization of her own perception of the Bayes risk. The information available to each agent is an initial belief, a private signal, and decisions of all earlier-acting agents; it is follows that each agent should apply a standard Bayesian update of her belief as in social learning. The effect of the set of initial beliefs on the decision-making performance of the last agent is studied. In general, the optimal initial beliefs are not equal to the actual prior probability. When the private signals are described by Gaussian likelihoods, they also are not haphazard, but rather follow a systematic pattern: The earlier-acting agents should act as if the prior probability is larger than it is in reality when the true prior probability is small, and vice versa. We interpret this as being open-minded toward the unlikely hypothesis. Such open-mindedness increases but does not maximize the mutual information between the true hypothesis and a decision.

For point-to-point and distributed communication of continuous sources, high-resolution quantization theory provides an achievable rate-distortion trade-off that is simple to compute and motivates practical compression architectures. Moreover, high-resolution analysis gives good inner bounds for the Shannon rate-distortion region when a more general characterization is difficult. In this paper, we analyze the sum-rate gap between coded nonuniform scalar quantization and the Shannon rate- distortion region for a system that requires fidelity in a computation applied to the source variables. We find that the loss can be as low as 0.255 bits/sample, which has previously been observed in the point-to-point setting, and it is achieved using a simple architecture of nonuniform quantization followed by Slepian-Wolf coding.

We present Mime, a compact, low-power 3D sensor for unencumbered free-form, single-handed gestural interaction with head-mounted displays (HMDs). Mime introduces a real-time signal processing framework that combines a novel three-pixel time-of-flight (TOF) module with a standard RGB camera. The TOF module achieves accurate 3D hand localization and tracking, and it thus enables motion-controlled gestures. The joint processing of 3D information with RGB image data enables finer, shape-based gestural interaction.

Several key results in distributed source coding offer the intuition that little improvement in compression can be gained from intersensor communication when the information is coded in long blocks. However, when sensors are restricted to code their observations in small blocks (e.g., one) or desire fidelity of a computation applied to source realizations, intelligent collaboration between sensors can greatly reduce distortion. For networks where sensors are allowed to "chat" using a side channel that is unobservable at the fusion center, we provide asymptotically-exact characterization of distortion performance and optimal quantizer design in the high-resolution (low-distortion) regime using a framework called distributed functional scalar quantization (DFSQ). The key result is that chatting can dramatically improve performance even when intersensor communication is at very low rate. We also solve the rate allocation problem when communication links have heterogeneous costs and provide a detailed example to demonstrate the theoretical and practical gains from chatting. This example for maximum computation gives insight on the gap between chatting and distributed networks, and how to optimize the intersensor communication.

The amount of calibration data needed to produce images of adequate quality can prevent auto-calibrating parallel imaging reconstruction methods like generalized autocalibrating partially parallel acquisitions (GRAPPA) from achieving a high total acceleration factor. To improve the quality of calibration when the number of auto-calibration signal (ACS) lines is restricted, we propose a sparsity-promoting regularized calibration method that finds a GRAPPA kernel consistent with the ACS fit equations that yields jointly sparse reconstructed coil channel images. Several experiments evaluate the performance of the proposed method relative to unregularized and existing regularized calibration methods for both low-quality and underdetermined fits from the ACS lines. These experiments demonstrate that the proposed method, like other regularization methods, is capable of mitigating noise amplification, and in addition, the proposed method is particularly effective at minimizing coherent aliasing artifacts caused by poor kernel calibration in real data. Using the proposed method, we can increase the total achievable acceleration while reducing degradation of the reconstructed image better than existing regularized calibration methods.

Active range acquisition systems such as light detection and ranging (LIDAR) and time-of-flight (TOF) cameras achieve high depth resolution but suffer from poor spatial resolution. In this paper we introduce a new range acquisition architecture that does not rely on scene raster scanning as in LIDAR or on a two-dimensional array of sensors as used in TOF cameras. Instead, we achieve spatial resolution through patterned sensing of the scene using a digital micromirror device (DMD) array. Our depth map reconstruction uses parametric signal modeling to recover the set of distinct depth ranges present in the scene. Then, using a convex program that exploits the sparsity of the Laplacian of the depth map, we recover the spatial content at the estimated depth ranges. In our experiments we acquired 64×64-pixel depth maps of fronto-parallel scenes at ranges up to 2.1 M using a pulsed laser, a DMD array and a single photon-counting detector. We also demonstrated imaging in the presence of unknown partially-transmissive occluders. The prototype and results provide promising directions for non-scanning, low-complexity range acquisition devices for various computer vision applications.

In this paper, we introduce a time-stampless adaptive nonuniform sampling (TANS) framework, in which time increments between samples are determined by a function of the m most recent increments and sample values. Since only past samples are used in computing time increments, it is not necessary to save sampling times (time stamps) for use in the reconstruction process. We focus on two TANS schemes for discrete-time stochastic signals: a greedy method, and a method based on dynamic programming. We analyze the performances of these schemes by computing (or bounding) their trade-offs between sampling rate and expected reconstruction distortion for Markovian signals. Simulation results support the analysis of the sampling schemes. We show that by opportunistically adapting to local signal characteristics TANS may lead to improved power efficiency in some applications.

Light detection and ranging (LIDAR) systems use time of flight (TOF) in combination with raster scanning of the scene to form depth maps, and TOF cameras instead make TOF measurements in parallel by using an array of sensors. Here we present a framework for depth map acquisition using neither raster scanning by the illumination source nor an array of sensors. Our architecture uses a spatial light modulator (SLM) to spatially pattern a temporally-modulated light source. Then, measurements from a single omnidirectional sensor provide adequate information for depth map estimation at a resolution equal that of the SLM. Proof-of-concept experiments have verified the validity of our modeling and algorithms.

Gaussian and quadratic approximations of message passing algorithms on graphs have attracted considerable attention due to their computational simplicity, analytic tractability, and wide applicability in optimization and statistical inference problems. This paper summarizes a systematic framework for incorporating such approximate message passing (AMP) methods in general graphical models. The key concept is a partition of dependencies of a general graphical model into strong and weak edges, with each weak edge representing a small, linearizable coupling of variables. AMP approximations based on the central limit theorem can be applied to the weak edges and integrated with standard message passing updates on the strong edges. The resulting algorithm, which we call hybrid generalized approximate message passing (Hybrid-GAMP), can yield significantly simpler implementations of sum-product and max-sum loopy belief propagation. By varying the partition between strong and weak edges, a performance-complexity trade-off can be achieved. Structured sparsity problems are studied as an example of this general methodology where there is a natural partition of edges.

Conventional imaging uses steady-state illumination and light sensing with focusing optics; variations of the light field with time are not exploited. We develop a signal processing framework for estimating the reflectance of a Lambertian planar surface in a known position using omnidirectional, time-varying illumination and unfocused, time-resolved sensing in place of traditional optical elements such as lenses and mirrors. Our model associates time sampling of the intensity of light incident at each sensor with a linear functional of . The discrete-time samples are processed to obtain -regularized estimates of . Improving on previous work, using nonimpulsive, bandlimited light sources instead of impulsive illumination significantly improves signal-to-noise ratio (SNR) and reconstruction quality. Our simulations suggest that practical diffuse imaging applications may be realized with commercially-available temporal light intensity modulators and sensors used in standard optical communication systems.

The replica method is a nonrigorous but well-known technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method, under the assumption of replica symmetry, to study estimators that are maximum a posteriori (MAP) under a postulated prior distribution. It is shown that with random linear measurements and Gaussian noise, the replica-symmetric prediction of the asymptotic behavior of the postulated MAP estimate of an -dimensional vector “decouples” as scalar postulated MAP estimators. The result is based on applying a hardening argument to the replica analysis of postulated posterior mean estimators of Tanaka and of Guo and Verdú. The replica-symmetric postulated MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, least absolute shrinkage and selection operator (LASSO), linear estimation with thresholding, and zero norm-regularized estimation. In the case of LASSO estimation, the scalar estimator reduces to a soft-thresholding operator, and for zero norm-regularized estimation, it reduces to a hard threshold. Among other benefits, the replica method provides a computationally tractable method for precisely predicting various performance metrics including mean-squared error and sparsity pattern recovery probability.

Given the possibility of communication systems failing catastrophically, we investigate limits to communicating over channels that fail at random times. These channels are finite-state semi-Markov channels. We show that communication with arbitrarily small probability of error is not possible. Making use of results in finite blocklength channel coding, we determine sequences of blocklengths that optimize transmission volume communicated at fixed maximum message error probabilities. We provide a partial ordering of communication channels. A dynamic programming formulation is used to show the structural result that channel state feedback does not improve performance.

The effect of quantization of prior probabilities in a collection of distributed Bayesian binary hypothesis testing problems over which the priors themselves vary is studied. In a setting with fusion of local binary decisions by majority rule, optimal local decision rules are discussed. Quantization is first considered under the constraint that agents employ identical quantizers. A method for design is presented that exploits an equivalence to a single-agent problem with a different likelihood function, the optimal quantizers are thus different than in the single-agent case. Removing the constraint of identical quantizers is demonstrated to improve performance. A method for design is presented that exploits an equivalence between agents having diverse K-level quantizers and agents having identical (3K-2)-level quantizers.

The effect of quantization of prior probabilities in a collection of distributed Bayesian binary hypothesis testing problems over which the priors themselves vary is studied, with focus on conflicting agents. Conflict arises from differences in Bayes costs, even when all agents desire correct decisions and agree on the meaning of correct. In a setting with fusion of local binary decisions by majority rule, Nash equilibrium local decision strategies are found. Assuming that agents follow Nash equilibrium decision strategies, designing quantizers for prior probabilities becomes a strategic form game, we discuss its Nash equilibria. We also propose two different constrained quantizer design games, find Nash equilibrium quantizer designs, and compare performance. The system has deadweight loss: equilibrium decisions are not Pareto optimal.

Quantizers for probabilistic sources are usually optimized for mean-squared error. In many applications, maintaining low relative error is a more suitable objective. This measure has previously been heuristically connected with the use of logarithmic companding in perceptual coding. We derive optimal companding quantizers for fixed rate and variable rate under high-resolution assumptions. The analysis shows logarithmic companding is optimal for variable-rate quantization but generally not for fixed-rate quantization. Naturally, the improvement in relative error from using a correctly optimized quantizer can be arbitrarily large. We extend this framework for a large class of nondifference distortions.

Both compressed sensing (CS) and parallel imaging effectively reconstruct magnetic resonance images from undersampled data. Combining both methods enables imaging with greater undersampling than accomplished previously. This paper investigates the choice of a suitable sampling pattern to accommodate both CS and parallel imaging. A combined method named SpRING is described and extended to handle random undersampling, and both GRAPPA and SpRING are evaluated for uniform and random undersampling using both simulated and real data. For the simulated data, when the undersampling factor is large, SpRING performs better with random undersampling. However, random undersampling is not as beneficial to SpRING for real data with approximate sparsity.

We consider the optimal quantization of compressive sensing measurements along with estimation from quantized samples using generalized approximate message passing (GAMP). GAMP is an iterative reconstruction scheme inspired by the belief propagation algorithm on bipartite graphs which generalizes approximate message passing (AMP) for arbitrary measurement channels. Its asymptotic error performance can be accurately predicted and tracked through the state evolution formalism. We utilize these results to design mean-square optimal scalar quantizers for GAMP signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers.

In cloud computing, storage area networks, and remote backup storage, stored data is modified with updates from new versions. It is desirable for the data to not only be compressed but to also be easily modified during updates, since representing information and modifying the representation are both expensive. A malleable coding scheme considers both compression efficiency and ease of alteration, promoting codeword reuse. We examine the trade-off between compression efficiency and malleability cost-the difficulty of synchronizing compressed versions-measured as the length of a reused prefix portion. Through a coding theorem, the region of achievable rates and malleability is expressed as a single-letter optimization. Relationships to common information problems are also described.

The distortion-rate performance of certain randomly-designed scalar quantizers is determined. The central results are the mean-squared error distortion and output entropy for quantizing a uniform random variable with thresholds drawn independently from a uniform distribution. The distortion is at most six times that of an optimal (deterministically-designed) quantizer, and for a large number of levels the output entropy is reduced by approximately (1-γ)/(ln 2) bits, where γ is the Euler-Mascheroni constant. This shows that the high-rate asymptotic distortion of these quantizers in an entropy-constrained context is worse than the optimal quantizer by at most a factor of 6e-2(1-γ)≈ 2.58.

Communication of quantized information is frequently followed by a computation. We consider situations of distributed functional scalar quantization: distributed scalar quantization of (possibly correlated) sources followed by centralized computation of a function. Under smoothness conditions on the sources and function, companding scalar quantizer designs are developed to minimize mean-squared error (MSE) of the computed function as the quantizer resolution is allowed to grow. Striking improvements over quantizers designed without consideration of the function are possible and are larger in the entropy-constrained setting than in the fixed-rate setting. As extensions to the basic analysis, we characterize a large class of functions for which regular quantization suffices, consider certain functions for which asymptotic optimality is achieved without arbitrarily fine quantization, and allow limited collaboration between source encoders. In the entropy-constrained setting, a single bit per sample communicated between encoders can have an arbitrarily large effect on functional distortion. In contrast, such communication has very little effect in the fixed-rate setting.

The replica method is a non-rigorous but widely-accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to analyze non-Gaussian maximum a posteriori (MAP) estimation. The main result is a counterpart to Guo and Verdú's replica analysis of minimum mean-squared error estimation. The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and zero norm-regularized estimation. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability.

We address theoptimal sensor arrangement problem, which is the determination of a geometric configuration of sensors such that the mean-squared error (MSE) in the estimation of an unknown trigonometric polynomial is minimum. Unsurprisingly, an arrangement in which sensors are spaced uniformly in each dimension is optimal. However, for multidimensional problems the minimum MSE is achieved with a much larger class of configurations that we callgeneralized regular arrangements. These arrangements are not necessarily generated by lattices and may exhibit great nonuniformity locally.

Permutation codes are a class of structured vector quantizers with a computationally-simple encoding procedure based on sorting the scalar components. Using a codebook comprising several permutation codes as subcodes preserves the simplicity of encoding while increasing the number of rate-distortion operating points, improving the convex hull of operating points, and increasing design complexity. We show that when the subcodes are designed with the same composition, optimization of the codebook reduces to a lower-dimensional vector quantizer design within a single cone. Heuristics for reducing design complexity are presented, including an optimization of the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook.

Sampling error due to jitter, or noise in the sample times, affects the precision of analog-to-digital converters in a significant, nonlinear fashion. In this paper, a polynomial least squares (PLS) estimator is derived for an observation model incorporating both independent jitter and additive noise, as an alternative to the linear least squares (LLS) estimator. After deriving this estimator, its implementation is discussed, and it is simulated using Matlab. In simulations, the PLS estimator is shown to improve the mean squared error performance by up to 30 percent versus the optimal linear estimator.

This paper considers a simple on-off random multiple access channel (MAC), where n users communicate simultaneously to a single receiver. Each user is assigned a single codeword which it transmits with some probability lambda over m degrees of freedom. The receiver must detect which users transmitted. We show that detection for this random MAC is mathematically equivalent to a standard sparsity detection problem. Using new results in sparse estimation we are able to estimate the capacity of these channels and compare the achieved performance of various detection algorithms. The analysis provides insight into the roles of power control and multi-user detection.

Permutation codes are a class of structured vector quantizers with a computationally-simple encoding procedure. In this paper, we provide an extension that preserves the computational simplicity but yields improved operational rate-distortion performance. The new class of vector quantizers has a codebook comprising several permutation codes as subcodes. Methods for designing good code parameters are given. One method depends on optimizing the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook.

Quantization is an important but often ignored consideration in discussions about compressed sensing. This paper studies the design of quantizers for random measurements of sparse signals that are optimal with respect to mean-squared error of the lasso reconstruction. We utilize recent results in high-resolution functional scalar quantization and homotopy continuation to approximate the optimal quantizer. Experimental results compare this quantizer to other practical designs and show a noticeable improvement in the operational distortion-rate performance.

A malleable coding scheme considers not only representation length but also ease of representation update, thereby encouraging some form of recycling to convert an old codeword into a new one. We examine the trade-off between compression efficiency and malleability cost, measured with a string edit distance that introduces a metric topology to the representation domain. We characterize the achievable rates and malleability as the solution of a subgraph isomorphism problem.

The replica method is a non-rigorous but widely-used technique from statistical physics used in the asymptotic analysis of many large random nonlinear problems. This paper applies the replica method to non-Gaussian MAP estimation. It is shown that with large random linear measurements and Gaussian noise, the asymptotic behavior of the MAP estimate of an n-dimensional vector ``decouples as n scalar MAP estimators. The result is a counterpart to Guo and Verdus replica analysis on MMSE estimation. The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding and zero-norm estimation. In the case of lasso estimation, the scalar estimator reduces to a soft-thresholding operator and for zero-norm estimation it reduces to a hard-threshold. Among other benefits, the replica method provides a computationally tractable method for exactly computing various performance metrics including MSE and sparsity recovery.

The paper considers the problem of detecting the sparsity pattern of a$k$-sparse vector in${\BBR }^{n}$from$m$random noisy measurements. A new necessary condition on the number of measurements for asymptotically reliable detection with maximum-likelihood (ML) estimation and Gaussian measurement matrices is derived. This necessary condition for ML detection is compared against a sufficient condition for simple maximum correlation (MC) or thresholding algorithms. The analysis shows that the gap between thresholding and ML can be described by a simple expression in terms of the total signal-to-noise ratio (SNR), with the gap growing with increasing SNR. Thresholding is also compared against the more sophisticated Lasso and orthogonal matching pursuit (OMP) methods. At high SNRs, it is shown that the gap between Lasso and OMP over thresholding is described by the range of powers of the nonzero component values of the unknown signals. Specifically, the key benefit of Lasso and OMP over thresholding is the ability of Lasso and OMP to detect signals with relatively small components.

Suppose a function of N real source variables X1N= (X1, X2, ..., XN) is desired at a destination constrained to receive a limited number of bits. If the result of evaluating the function, Y = G(X1N), can be itself encoded, this is the optimal strategy-the origin of Y becomes irrelevant to the communication problem. We consider two alternative scenarios: distributed quantization, in which each Ximust be separately encoded; and linear transform coding of X1N. Optimal fixed- and variable-rate scalar quantizers are derived under the conventional assumptions of high-resolution quantization theory, and we find optimal transforms for transform coding. For certain classes of functions, examples demonstrate large improvements over using quantizers designed to minimize distortion of the Xis.

The use of subspace structure in source and channel coding is studied. We show that for source coding of an i.i.d. Gaussian source, restriction of the codebook to a union of subspaces need not induce any performance penalty. In fact, in N-dimensional space, a two-stage quantization of first projecting to the nearest of J subspaces of dimension K in a random first-stage codebook of subspaces, followed by quantizing to the nearest of codewords in a second-stage codebook within the K-dimensional subspace induces no performance loss. This structure allows the rate-distortion bound to be approached asymptotically with block length N. The dual results for channel coding are explicitly described: for an additive white Gaussian noise channel, we introduce a particular subspace-based codebook that induces no rate loss, and the Shannon capacity is achieved. While this has complexity exponential in N, it is reduced from an unstructured search.

Recent research suggests that neural systems employ sparse coding. However, there is limited theoretical understanding of fundamental resolution limits in such sparse coding. This paper considers a general sparse estimation problem of detecting the sparsity pattern of a $k$-sparse vector in $\R^n$ from $m$ random noisy measurements. Our main results provide necessary and sufficient conditions on the problem dimensions, $m$, $n$ and $k$, and the signal-to-noise ratio (SNR) for asymptotically-reliable detection. We show a necessary condition for perfect recovery at any given SNR for all algorithms, regardless of complexity, is $m = \Omega(k\log(n-k))$ measurements. This is considerably stronger than all previous necessary conditions. We also show that the scaling of $\Omega(k\log(n-k))$ measurements is sufficient for a trivial ``maximum correlation'' estimator to succeed. Hence this scaling is optimal and does not require lasso, matching pursuit, or more sophisticated methods, and the optimal scaling can thus be biologically plausible.

We introduce a novel algorithm for the design of fast slice-selective spatially-tailored magnetic resonance imaging (MRI) excitation pulses. This method, based on sparse approximation theory, uses a second-order cone optimization to place and modulate a small number of slice-selective sinc-like radio-frequency (RF) pulse segments ("spokes") in excitation k-space, enforcing sparsity on the number of spokes allowed while simultaneously encouraging those that remain to be placed and modulated in a way that best forms a user-defined in-plane target magnetization. Pulses are designed to mitigate B(1) inhomogeneity in a water phantom at 7 T and to produce highly-structured excitations in an oil phantom on an eight-channel parallel excitation system at 3 T. In each experiment, pulses generated by the sparsity-enforced method outperform those created via conventional Fourier-based techniques, e.g., when attempting to produce a uniform magnetization in the presence of severe B(1) inhomogeneity, a 5.7-ms 15-spoke pulse generated by the sparsity-enforced method produces an excitation with 1.28 times lower root mean square error than conventionally-designed 15-spoke pulses. To achieve this same level of uniformity, the conventional methods need to use 29-spoke pulses that are 7.8 ms long.

Encouraging recent results in compressed sensing or compressive sampling suggest that a set of inner products with random measurement vectors forms a good representation of a source vector that is known to be sparse in some fixed basis. With quantization of these inner products, the encoding can be considered universal for sparse signals with known sparsity level. We analyze the operational rate-distortion performance of such source coding both with genie-aided knowledge of the sparsity pattern and maximum likelihood estimation of the sparsity pattern. We show that random measurements induce an additive logarithmic rate penalty, i.e., at high rates the performance with rate R + O(log R) and random measurements is equal to the performance with rate R and deterministic measurements matched to the source.

This paper introduces a family of integer-to-integer approximations to the Cartesian-to-polar coordinate transformation and analyzes its application to lossy compression. A high-rate analysis is provided for an encoder that first uniformly scalar quantizes, then transforms to "integer polar coordinates," and finally separately entropy codes angle and radius. For sources separable in polar coordinates, the performance (at high rate) is shown to match that of entropy-constrained unconstrained polar quantization - where the angular quantization is allowed to depend on the radius. Thus, for sources separable in polar coordinates but not separable in rectangular coordinates - including certain Gaussian scale mixtures - the proposed system performs better than any transform code. Furthermore, unlike unconstrained polar quantization, integer polar coordinates are appropriate for lossless compression of integer-valued vectors. Combination of integer polar coordinates with integer-to-integer transform coding is also discussed.

Summary form only given. We designed a family of integer-to-integer (i2i) approximations to the Cartesian-to-polar transformation and analyzed its behavior for high-rate transform coding. Denoting (ordinary, continuous) polar coordinates by (r, 0), our precise high-rate analysis relates the performance to the differential entropies of r2and 0, which are often easy to evaluate. One may thus predict when there is an improvement over linear transform coding. The analysis matches our simulations for coding of Gaussian scale mixtures and other polar-separable sources. The advantage over the best linear transform coder can be large. Our hope is to extend the polar-coordinate results to a general theory for nonlinear transform coding based on i2i implementations of arbitrary nonlinear transformations

The problem of communicating (unordered) sets, rather than (ordered) sequences is formulated. Elementary results in all major branches of source coding theory, including lossless coding, high-rate and low-rate quantization, and rate distortion theory are presented. In certain scenarios, rate savings of log n! bits for sets of size n are obtained. Asymptotically in the set size, the entropy rate is zero and for sources with an ordered parent alphabet, the (0,0) point is the rate distortion function.

Recently the sampling theory for certain parametric signals based on rate of innovation has been extended to all sampling kernels that satisfy the Strang-Fix conditions, thus including many attractive choices with finite support. We propose a new sampling scheme in which samples are taken simultaneously at the outputs of multiple channels. This new scheme is closely related to previously known cases, but provides a successive approximation property that can be used for detecting undermodeling. We also draw connections to splines and multi-scale sampling of signals.

In this paper, we present two novel algorithms for denoising hyperspectral data. Each algorithm exploits correlation between bands by enforcing simultaneous sparsity on their wavelet representations. This is done in a non-linear manner using wavelet decompositions and sparse approximation techniques. The first algorithm denoises an entire cube of data. Our experiments show that it outperforms wavelet-based global soft thresholding techniques in both a mean-square error (MSE) and a qualitative visual sense. The second algorithm denoises a set of noisy, user designated bands ("junk bands") by exploiting correlated information from higher quality bands within the same cube. We prove the utility of our junk band denoising algorithm by denoising ten bands of actual AVIRIS data by a significant amount. Preprocessing data cubes with these algorithms is likely to increase the performance of classifiers that make use of hyperspectral data, especially if the denoised and/or recovered bands contain spectral features useful for discriminating between classes.

If a signal x is known to have a sparse representation with respect to a frame, the signal can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. This paper analyzes the mean squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal. The first main result is an MSE bound that depends on a new bound on approximating a Gaussian signal as a linear combination of elements of an overcomplete dictionary. This bound may be of independent interest for source coding. Further analyses are for dictionaries generated randomly according to a spherically-symmetric distribution and signals expressible with single dictionary elements. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. In the limit of large dimension, these approximations have simple forms. The asymptotic expressions reveal a critical input signal-to-noise ratio (SNR) for signal recovery

This paper proposes an encoding method for high-quality, low-delay audio communication that is robust to losses in packetized transmission. Robustness is provided by a multiple description vector quantization (MDVQ) technique that is designed to minimize the mean-squared error (MSE). The key to applying this technique effectively is the use of psycho-acoustically controlled preand post-filters that make the mean-squared quantization error perceptually relevant. Experiments show that the MDVQ-based encoder yields better results-in both MSE and subjective audio quality-than simple alternative coders with the same low delay.

Consider a communication system in which a filtered and quantized signal is sent over a channel with erasures and (potentially) additive noise. Linear MMSE estimation is achieved in such a system by Kalman filtering. Allowing any Markov erasure process and any Markov-state jump linear signal generation model, it is shown that the estimation performance at the receiver can be computed as a deterministic optimization with linear matrix inequality (LMl) constraints rather than a pseudorandom simulation. Furthermore, in contrast to the case without erasures, the filtering in the transmitter should not necessarily be MMSE prediction (whitening); a procedure is given to find a locally optimal prefilter. The main tools are recent LMI characterizations of asymptotic state estimation error covariance and output estimation error variance for discrete-time jump linear systems in which the discrete portion of the system state is a Markov chain. As another application of this framework, a novel analysis and optimization of a "streaming" version of multiple description coding based on subsampling is outlined.

Due to constraints in cost, power, and communication, losses often arise in large sensor networks. The sensor can be modeled as an output of a linear stochastic system with random losses of the sensor output samples. This paper considers the general problem of state estimation for jump linear systems where the discrete transitions are modeled as a Markov chain. Among other applications, this rich model can be used to analyze sensor networks. The sensor loss events are then modeled as Markov processes. Under the jump linear system model, many types of underlying losses can be easily considered, and the optimal estimator to be performed at the receiver in the presence of missing sensor data samples is given by a standard time-varying Kalman filter.We show that the asymptotic average estimation error variance converges and is given by a Linear Matrix Inequality, which can be easily solved. Under this framework, any arbitrary Markov loss process can be modeled, and its average asymptotic error variance can be directly computed. We include a few illustrative examples including .xed-length burst errors, a two-state model,and partial losses due to multiple SNR states. Our analysis encompasses modeling discrete changes not only in the received data as stated above, but also in the underlying system. In the context of the lossy sensor model, the former allows for variation in sensor positioning, power control, and loss of data communications; the latter could allow for discrete changes in the dynamics of the variable monitored by the sensor. This freedom in modeling yields a tool that is potentially valuable in various scenarios in which entities that share information are subjected to challenging and time-varying network conditions.

This work is focused on computing-via a deterministic optimization with linear matrix inequality (LMI) constraints, rather than a pseudorandom simulation-the performance of predictive quantization schemes under various scenarios for loss and degradation of encoded prediction error samples. The ability to make this computation then allows for the optimization of prediction filters with the aim of minimizing overall mean squared error (including the effects of losses) rather than to minimize the variance of the unquantized prediction error sequence. The main tools are recent characterizations of asymptotic state estimation error covariance and output estimation error variance in terms of LMIs. These characterizations apply to discrete-time jump linear systems in which the discrete portion of the system state is a Markov chain. Translating to the signal processing terminology, this means that the signal model is "piecewise ARMA," as is standard in many forms of speech processing.

Despite their simplicity, scalar threshold operators effectively remove additive white Gaussian noise from wavelet detail coefficients of many practical signals. This paper explores the use of multivariate estimators that are almost as simple as scalar threshold operators. Sendur and Selesnick (2002) have recently shown the effectiveness of joint threshold estimation of parent and child wavelet coefficients. This paper discusses analogous results in two situations. With a frame representation, a simple joint threshold estimator is derived and it is shown that its generalization is equivalent to a type of l/sub 1/-regularized denoising. Then, for the case where multiple independent noisy observations are available, the counter-intuitive results by Chang, Yu, and Vetterli (2000) on combining averaging and thresholding are explained as a fortuitous consequence of randomization.

An achievable region for the L-channel multiple description coding problem is presented. This region generalizes two-channel results of El Gamal and Cover (1982) and of Zhang and Berger (1987). It further generalizes three-channel results of Gray and Wyner (1974) and of Zhang and Berger. A source that is successively refinable on chains is shown to be successively refinable on trees. A new outer bound on the rate-distortion (RD) region for memoryless Gaussian sources with mean squared error distortion is also derived. The achievable region meets this outer bound for certain symmetric cases.

Coupling the periodic time-invariance of the wavelet transform, with a view to thresholding as a projection, yields a simple, recursive, wavelet-based technique for denoising signals. Estimating a signal from a noise-corrupted observation is a fundamental problem of signal processing which has been addressed via many techniques. Previously, R.R. Coifman and D.L. Donoho (see Wavelets and Statistics, Lecture Notes in Statistics, vol.103, p.125-50, 1995) introduced cycle spinning, a technique of estimating the true signal as the linear average of individual estimates derived from wavelet-thresholded translated versions of the noisy signal. We demonstrate that such an average can be improved upon dramatically. The proposed algorithm recursively "cycle spins" by repeatedly translating and denoising the input via basic wavelet denoising and then translating back; at each iteration, the output of the previous iteration is used as input. Exploiting the convergence properties of projections, our algorithm can be regarded as a sequence of denoising projections that converge to the projection of the original noisy signal to a small subspace containing the true signal. It is proven that the algorithm is guaranteed to converge globally, and simulations on piecewise polynomial signals show marked improvement over both basic wavelet thresholding and standard cycle spinning.

This paper introduces Wave and Equation Based Rate Control (WEBRC), the first multiple rate multicast congestion control protocol to be equation based. The equation-based approach enforces fairness to TCP with the benefit that fluctuations in the flow rate are small in comparison to TCP.This paper also introduces the multicast round trip time (MRTT), a multicast analogue of the unicast round trip time (RTT). The MRTT is fundamental to the equation-based protocol that each receiver uses to adjust its reception rate. Each receiver independently measures its own MRTT without placing any added messaging burden on the receiver, the sender or the intermediate network elements. Benefits provided by the MRTT include those that the RTT provides to TCP, e.g., reduced reception rates in reaction to buffer filling and fair sharing of bottleneck links. In addition, the use of MRTT is shown to synchronize and equalize the reception rates of proximate receivers and to cause reception rates to increase as the density of receivers increases.Another innovation of WEBRC is the idea of transmitting data with waves: the transmission rate on a channel is periodic, with an exponentially decreasing form during an active period followed by a quiescent period. Benefits of using waves include insensitivity to large IGMP leave latency; a frequency of joins and leaves by each receiver that is small and independent of the receiver reception rate; the use of a small number of multicast channels; fine-grained control over the receiver reception rate; and minimal, at times nonexistent, losses due to buffer overflow.

A multiple description (MD) lattice vector quantization technique for two descriptions was previously introduced in which fine and coarse codebooks are both lattices. The encoding begins with quantization to the nearest point in the fine lattice. This encoding is an inherent optimization for the decoder that receives both descriptions; performance can be improved with little increase in complexity by considering all decoders in the initial encoding step. The altered encoding relies only on the symmetries of the coarse lattice. This allows us to further improve performance without a significant increase in complexity by replacing the fine lattice codebook with a nonlattice codebook that respects many of the symmetries of the coarse lattice. Examples constructed with the two-dimensional (2-D) hexagonal lattice demonstrate large improvement over time sharing between previously known quantizers.

We study frames for robust transmission over the Internet. In our previous work, we used quantized finite-dimensional frames to achieve resilience to packet losses; here, we allow the input to be a sequence in l/sub 2/(Z) and focus on a filter-bank implementation of the system. We present results in parallel, R/sup N/ or C/sup N/ versus l/sub 2/(Z), and show that uniform tight frames, as well as newly introduced strongly uniform tight frames, provide the best performance.

Oversampled filter banks can be used to enhance resilience to erasures in communication systems in much the same way that finite-dimensional frames have previously been applied. This paper extends previous finite dimensional treatments to frames and signals in l/sub 2/(Z) with frame expansions that can be implemented efficiently with filter banks. It is shown that tight frames attain best performance. In particular, if encoding with a uniform frame, the quantization error is minimized if and only if the frame is tight. In case of one erasure and if encoding with a strongly uniform frame, tight frames are still optimal. In case of more erasures, an expression for the mean square error is given and some general considerations are presented.

New achievability results for the L-stage successive refinement problem with L>2 are presented. These are derived from a recent achievability result for the more general problem of multiple description (MD) coding with L>2 channels. It is shown that successive refinability on chains implies successive refinability on trees and that memoryless Gaussian sources are successively refinable on chains and trees.

Multiple description (MD) coding is source coding in which several descriptions of the source are produced such that various reconstruction qualities are obtained from different subsets of the descriptions. Unlike multiresolution or layered source coding, there is no hierarchy of descriptions; thus, MD coding is suitable for packet erasure channels or networks without priority provisions. Generalizing work by Orchard, Wang, Vaishampayan and Reibman (see Proc IEEE Int. Conf. Image Processing, vol.I, Santa Barbara, CA, p.608-11, 1997), a transform-based approach is developed for producing M descriptions of an N-tuple source, M/spl les/N. The descriptions are sets of transform coefficients, and the transform coefficients of different descriptions are correlated so that missing coefficients can be estimated. Several transform optimization results are presented for memoryless Gaussian sources, including a complete solution of the N=2, M=2 case with arbitrary weighting of the descriptions. The technique is effective only when independent components of the source have differing variances. Numerical studies show that this method performs well at low redundancies, as compared to uniform MD scalar quantization.

Permutation codes are vector quantizers whose codewords are related by permutations and, in one variant, sign changes. Asymptotically, as the vector dimension grows, optimal Variant I permutation code design is identical to optimal entropy-constrained scalar quantizer (ECSQ) design. However, contradicting intuition and previously published assertions, there are finite block length permutation codes that perform better than the best ones with asymptotically large length; thus, there are Variant I permutation codes whose performances cannot be matched by any ECSQ. Along similar lines, a new asymptotic relation between Variant I and Variant II permutation codes is established but again demonstrated to not necessarily predict the performances of short codes. Simple expressions for permutation code performance are found for memoryless uniform and Laplacian sources. The uniform source yields the aforementioned counterexamples.

Estimation problems with bounded, uniformly distributed noise arise naturally in reconstruction problems from over complete linear expansions with subtractive dithered quantization. We present a simple recursive algorithm for such bounded-noise estimation problems. The mean-square error (MSE) of the algorithm is "almost" O(1/n/sup 2/), where n is the number of samples. This rate is faster than the O(1/n) MSE obtained by standard recursive least squares estimation and is optimal to within a constant factor.

Multiple description lattice vector quantization (MDLVQ) is a technique for two-channel multiple description coding. We observe that MDLVQ, in the form introduced by Servetto et al. (1999), is inherently optimized for the central decoder; i.e., for zero probability of a lost description. With a nonzero probability of description loss, performance is improved by modifying the encoding rule (using nearest neighbors with respect to "multiple description distance") and by perturbing the lattice codebook. The perturbation maintains many symmetries and hence does not significantly affect encoding or decoding complexity. An extension to more than two descriptions with attractive decoding properties is outlined.

In audio communication over a lossy packet network, concealment techniques are used to mitigate the effects of lost packets. This concealment is markedly improved if the compressed representation retains redundancy to aid in the estimation of lost information. A perceptual audio coder employing multiple description correlating transforms demonstrates this phenomenon.

A new interpretation of transform coding is developed that downplays quantization and emphasizes entropy coding, allowing a comparison of entropy coding methods with different memory requirements. With conventional transform coding, based on computing Karhunen-Loeve transform coefficients and then quantizing them, vector entropy coding can be replaced by scalar entropy coding without an increase in rate. Thus the transform coding advantage is a reduction in memory requirements for entropy coding. This paper develops a transform coding technique where the source samples are first scalar-quantized and then transformed with an integer-to-integer approximation to a nonorthogonal linear transform. Among the possible advantages is to reduce the memory requirement further than conventional transform coding by using a single common scalar entropy codebook for all components. The analysis shows that for high-rate coding of a Gaussian source, this reduction in memory requirements comes without any degradation of rate-distortion performance.

The Karhunen-Loeve transform (KLT) is optimal for transform coding of a Gaussian source. This is established for all scale-invariant quantizers, generalizing previous results. A backward adaptive technique for combating the data dependence of the KLT is proposed and analyzed. When the adapted transform converges to a KLT, the scheme is universal among transform coders. A variety of convergence results are proven.

Quantized frame expansions are proposed as a method for generalized multiple description coding, where each quantized coefficient is a description. Whereas previous investigations have revealed the robustness of frame expansions to additive noise and quantization, this represents a new application of frame expansions. The performance of a system based on quantized frame expansions is compared to that of a system with a conventional block channel code. The new system performs well when the number of lost descriptions (erasures on an erasure channel) is hard to predict.

Multiple description coding (MDC) is source coding for multiple channels such that a decoder which receives an arbitrary subset of the channels may produce a useful reconstruction. Orchard et al. (1997) proposed a transform coding method for MDC of pairs of independent Gaussian random variables. This paper provides a general framework which extends multiple description transform coding (MDTC) to any number of variables and expands the set of transforms which are considered. Analysis of the general case is provided, which can be used to numerically design optimal MDTC systems. The case of two variables sent over two channels is analytically optimized in the most general setting where channel failures need not have equal probability or be independent. It is shown that when channel failures are equally probable and independent, the transforms used in Orchard et al. are in the optimal set, but many other choices are possible. A cascade structure is presented which facilitates low-complexity design, coding, and decoding for a system with a large number of variables.

Generalized multiple description coding (GMDC) is source coding for multiple channels such that a decoder which receives an arbitrary subset of the channels may produce a useful reconstruction. This paper reports on applications of two recently proposed methods for GMDC to image coding. The first produces statistically correlated streams such that lost streams can be estimated from the received data. The second uses quantized frame expansions and hence is conceptually similar to block channel coding, except it is done prior to quantization.

Coefficient quantization has peculiar qualitative effects on representations of vectors in IR with respect to overcomplete sets of vectors. These effects are investigated in two settings: frame expansions (representations obtained by forming inner products with each element of the set) and matching pursuit expansions (approximations obtained by greedily forming linear combinations). In both cases, based on the concept of consistency, it is shown that traditional linear reconstruction methods are suboptimal, and better consistent reconstruction algorithms are given. The proposed consistent reconstruction algorithms were in each case implemented, and experimental results are included. For frame expansions, results are proven to bound distortion as a function of frame redundancy r and quantization step size for linear, consistent, and optimal reconstruction methods. Taken together, these suggest that optimal reconstruction methods will yield O(1/r/sup 2/) mean-squared error (MSE), and that consistency is sufficient to insure this asymptotic behavior. A result on the asymptotic tightness of random frames is also proven. Applicability of quantized matching pursuit to lossy vector compression is explored. Experiments demonstrate the likelihood that a linear reconstruction is inconsistent, the MSE reduction obtained with a nonlinear (consistent) reconstruction algorithm, and generally competitive performance at low bit rates.

The method for universal transform coding based on backward adaptation introduced by Goyal et al. (see IEEE Int. Conf. Image Proc., vol.II, p.365-8, 1996) is reviewed and further analyzed. This algorithm uses a linear transform which is periodically updated based on a local Karhunen-Loeve transform (KLT) estimate. The KLT estimate is derived purely from quantized data, so the decoder can track the encoder state without any side information. The effect of estimating only from quantized data is quantitatively analyzed. Two convergence results which hold in the absence of estimation noise are presented. The first applies for any vector dimension but does not preclude the necessity of a sequence of quantization step sizes that goes to zero. The second applies only in the two-dimensional case, but shows local convergence for a fixed, sufficiently small quantization step size. Refinements which reduce the storage and computational requirements of the algorithm are suggested.

A distortion-computation function D(C) is defined as the minimum expected distortion in computing some quantity while using no more than C computational units. In a communication framework, where the computational problem is to determine a representation that can be transmitted with expected rate not exceeding R, this gives slices of a rate-distortion-computation surface. The convexity of distortion-computation functions and rate-distortion-computation surfaces is asserted. Transform coding is studied as a particular instance of this theory. Explicit comparisons between the efficacies of the Karhunen-Loeve transform and the discrete cosine transform for coding of a Gauss-Markov source are given. Results are also given on joint optimization of the block length and the computational precision.

This paper explores the effects of coefficient quantization in applying the matching pursuit algorithm to source coding of vectors in R/sup N/. By considering the issue of consistency, we find that even though matching pursuit is designed to produce a linear combination to estimate a given source vector, optimal reconstruction in the presence of coefficient quantization requires a nonlinear algorithm. Such an algorithm was implemented and was experimentally confirmed to have superior reconstruction properties in comparison to the standard linear reconstruction. The improvement depends on the source, dictionary and operating point; in some cases the MSE was lessened by as much as a factor of five.

LCAV

We present a method that represents a signal with respect to an overcomplete set of vectors which we call a dictionary. The use of overcomplete sets of vectors (redundant bases or frames) together with quantization is explored as an alternative to transform coding for signal compression. The goal is to retain the computational simplicity of transform coding while adding flexibility like adaptation to signal statistics. We show results using both fixed quantization in frames and greedy quantization using matching pursuit. An MSE slope of -6 dB/octave of frame redundancy is shown for a particular tight frame and is verified experimentally for another frame.