Underwater acoustic environment estimation is a challenging but important task for remote sensing scenarios. Current estimation methods require high signal strength and a solution to the fragile echo labeling problem to be effective. In previous publications, we proposed a general deep learning-based method for two-dimensional environment estimation which outperformed the state-of-the-art, both in simulation and in real-life experimental settings. A limitation of this method was that some prior information had to be provided by the user on the number and locations of the reflective boundaries, and that its neural networks had to be re-trained accordingly for different environments. Utilizing more advanced neural network and time delay estimation techniques, the proposed improved method no longer requires prior knowledge the number of boundaries or their locations, and is able to estimate two-dimensional environments with one or two boundaries. Future work will extend the proposed method to more boundaries and larger-scale environments.

We develop Latent Exploration Score (LES) to mitigate over-exploration in Latent Space Optimization (LSO), a popular method for solving black-box discrete optimization problems. LSO utilizes continuous optimization within the latent space of a Variational Autoencoder (VAE) and is known to be susceptible to over-exploration, which manifests in unrealistic solutions that reduce its practicality. LES leverages the trained decoder’s approximation of the data distribution, and can be employed with any VAE decoder–including pretrained ones–without additional training, architectural changes or access to the training data. Our evaluation across five LSO benchmark tasks and twenty-two VAE models demonstrates that LES always enhances the quality of the solutions while maintaining high objective values, leading to improvements over existing solutions in most cases. We believe that new avenues to LSO will be opened by LES’ ability to identify out of distribution areas, differentiability, and computational tractability.

State-Space Models (SSMs) have proven to be powerful tools for online function approximation and for modeling long-range dependencies in sequential data. While recent methods such as HiPPO have demonstrated strong performance using a few polynomial bases, they remain limited by their reliance on closed-form solutions for specific, well-behaved bases. The SaFARi framework generalizes this approach, enabling the construction of SSMs from arbitrary frames, including non-orthogonal and redundant ones, thus allowing an infinite diversity of possible "species'' within the SSM family. In this paper, we introduce WaLRUS (Wavelets for Long-range Representation Using SSMs), a new species of SaFARi built from Daubechies wavelet frames. We instantiate two variants, scaled-Walrus and translated-Walrus, and show that their multiresolution and localized nature offers significant advantages in representing non-smooth and transient signals. We compare Walrus to HiPPO-based models and demonstrate improved accuracy, better numerical properties, and more efficient implementations for online function approximation tasks.

We study the interpolation capabilities of implicit neural representations (INRs) of images. In principle, INRs promise a number of advantages, such as continuous derivatives and arbitrary sampling, being freed from the restrictions of a raster grid. However, empirically, INRs have been observed to poorly interpolate between the pixels of the fit image; in other words, they do not inherently possess a suitable prior for natural images. In this paper, we propose to address and improve INRs’ interpolation capabilities by explicitly integrating image prior information into the INR architecture via deep decoder, a specific implementation of the deep image prior (DIP). Our method, which we call TITAN, leverages a residual connection from the input which enables integrating the principles of the grid-based DIP into the grid-free INR. Through super-resolution and computed tomography experiments, we demonstrate that our method significantly improves upon classic INRs, thanks to the induced natural image bias. We also find that by constraining the weights to be sparse, image quality and sharpness are enhanced, increasing the Lipschitz constant.

Seismic advances in generative AI algorithms for imagery, text, and other data types have led to the temptation to use AI-synthesized data to train next-generation models. Repeating this process creates an autophagous ("self-consuming") loop whose properties are poorly understood. We conduct a thorough analytical and empirical analysis using state-of-the-art generative image models of three families of autophagous loops that differ in how fixed or fresh real training data is available through the generations of training and whether the samples from previous-generation models have been biased to trade off data quality versus diversity. Our primary conclusion across all scenarios is that *without enough fresh real data in each generation of an autophagous loop, future generative models are doomed to have their quality (precision) or diversity (recall) progressively decrease.* We term this condition Model Autophagy Disorder (MAD), by analogy to mad cow disease, and show that appreciable MADness arises in just a few generations.

Implicit neural representations (INRs) have arisen as useful methods for representing signals on Euclidean domains. By parameterizing an image as a multilayer perceptron (MLP) on Euclidean space, INRs effectively couple spatial and spectral features of the represented signal in a way that is not obvious in the usual discrete representation. Although INRs using sinusoidal activation functions have been studied in terms of Fourier theory, recent works have shown the advantage of using wavelets instead of sinusoids as activation functions, due to their ability to simultaneously localize in both frequency and space. In this work, we approach such INRs and demonstrate how they resolve high-frequency features of signals from coarse approximations performed in the first layer of the MLP. This leads to multiple prescriptions for the design of INR architectures, including the use of progressive wavelets, decoupling of low and high-pass approximations, and initialization schemes based on the singularities of the target signal.

Grokking, or delayed generalization, is a phenomenon where generalization in a deep neural network (DNN) occurs long after achieving near zero training error. Previous studies have reported the occurrence of grokking in specific controlled settings, such as DNNs initialized with large-norm parameters or transformers trained on algorithmic datasets. We demonstrate that grokking is actually much more widespread and materializes in a wide range of practical settings, such as training of a convolutional neural network (CNN) on CIFAR10 or a Resnet on Imagenette. We introduce the new concept of delayed robustness, whereby a DNN groks adversarial examples and becomes robust, long after interpolation and/or generalization. We develop an analytical explanation for the emergence of both delayed generalization and delayed robustness based on the local complexity of a DNN’s input-output mapping. Our local complexity measures the density of so-called “linear regions’’ (aka, spline partition regions) that tile the DNN input space and serves as a utile progress measure for training. We provide the first evidence that, for classification problems, the linear regions undergo a phase transition during training whereafter they migrate away from the training samples (making the DNN mapping smoother there) and towards the decision boundary (making the DNN mapping less smooth there). Grokking occurs post phase transition as a robust partition of the input space thanks to the linearization of the DNN mapping around the training points. Web: https://bit.ly/grok-adversarial.

In this work, we address two main shortcomings of transformer architectures: input corruption and rank collapse in their output representation. We unveil self-attention as an autonomous state-space model that inherently promotes smoothness in its solutions, leading to lower-rank outputs and diminished representation capacity. Moreover, the steady-state solution of the model is sensitive to input perturbations. We incorporate a Proportional-Integral-Derivative (PID) closed-loop feedback control system with a reference point into the model to improve robustness and representation capacity. This integration aims to preserve high-frequency details while bolstering model stability, rendering it more noise-resilient. The resulting controlled state-space model is theoretically proven robust and adept at addressing the rank collapse. Motivated by this control framework, we derive a novel class of transformers, PID-controlled Transformer (PIDformer), aimed at improving robustness and mitigating the rank-collapse issue inherent in softmax transformers. We empirically evaluate the model for advantages and robustness against baseline transformers across various practical tasks, including object classification, image segmentation, and language modeling.

High-quality conversational datasets are crucial for the successful development of Intelligent Tutoring Systems (ITS) that utilize a Large Language Model (LLM) backend. Synthetic student-teacher dialogues, generated using advanced GPT-4 models, are a common strategy for creating these datasets. However, subjects like physics that entail complex calculations pose a challenge. While GPT-4 presents impressive language processing capabilities, its limitations in fundamental mathematical reasoning curtail its efficacy for such subjects. To tackle this limitation, we introduce in this paper an innovative stateful prompt design. Our design orchestrates a mock conversation where both student and tutorbot roles are simulated by GPT-4. Each student response triggers an internal monologue, or ‘code soliloquy’ in the GPT-tutorbot, which assesses whether its subsequent response would necessitate calculations. If a calculation is deemed necessary, it scripts the relevant Python code and uses the Python output to construct a response to the student. Our approach notably enhances the quality of synthetic conversation datasets, especially for subjects that are calculation-intensive. The preliminary Subject Matter Expert evaluations reveal that our Higgs model, a fine-tuned LLaMA model, effectively uses Python for computations, which significantly enhances the accuracy and computational reliability of Higgs’ responses.

Implicit neural representations (INRs) have demonstrated success in a variety of applications, including inverse problems and neural rendering. An INR is typically trained to capture one signal of interest, resulting in learned neural features that are highly attuned to that signal. Assumed to be less generalizable, we explore the aspect of transferability of such learned neural features for fitting similar signals. We introduce a new INR training framework, STRAINER that learns transferable features for fitting INRs to new signals from a given distribution, faster and with better reconstruction quality. Owing to the sequential layer-wise affine operations in an INR, we propose to learn transferable representations by sharing initial encoder layers across multiple INRs with independent decoder layers. At test time, the learned encoder representations are transferred as initialization for an otherwise randomly initialized INR. We find STRAINER to yield extremely powerful initialization for fitting images from the same domain and allow for a ≈ +10dB gain in signal quality early on compared to an untrained INR itself. STRAINER also provides a simple way to encode data-driven priors in INRs. We evaluate STRAINER on multiple in-domain and out-of-domain signal fitting tasks and inverse problems and further provide detailed analysis and discussion on the transferability of STRAINER’s features.

DeepTensor is a computationally efficient framework for low-rank decomposition of matrices and tensors using deep generative networks. We decompose a tensor as the product of low-rank tensor factors (e.g., a matrix as the outer product of two vectors), where each low-rank tensor is generated by a deep network (DN) that is trained in a self-supervised manner to minimize the mean-square approximation error. Our key observation is that the implicit regularization inherent in DNs enables them to capture nonlinear signal structures (e.g., manifolds) that are out of the reach of classical linear methods like the singular value decomposition (SVD) and principal components analysis (PCA). Furthermore, in contrast to the SVD and PCA, whose performance deteriorates when the tensor's entries deviate from additive white Gaussian noise, we demonstrate that the performance of DeepTensor is robust to a wide range of distributions. We validate that DeepTensor is a robust and computationally efficient drop-in replacement for the SVD, PCA, nonnegative matrix factorization (NMF), and similar decompositions by exploring a range of real-world applications, including hyperspectral image denoising, 3D MRI tomography, and image classification. In particular, DeepTensor offers a 6 dB signal-to-noise ratio improvement over standard denoising methods for signal corrupted by Poisson noise and learns to decompose 3D tensors 60 times faster than a single DN equipped with 3D convolutions.

The first step toward investigating the effectiveness of a treatment via a randomized trial is to split the population into control and treatment groups then compare the average response of the treatment group receiving the treatment to the control group receiving the placebo. To ensure that the difference between the two groups is caused only by the treatment, it is crucial that the control and the treatment groups have similar statistics. Indeed, the validity and reliability of a trial are determined by the similarity of two groups' statistics. Covariate balancing methods increase the similarity between the distributions of the two groups' covariates. However, often in practice, there are not enough samples to accurately estimate the groups' covariate distributions. In this article, we empirically show that covariate balancing with the standardized means difference (SMD) covariate balancing measure, as well as Pocock and Simon's sequential treatment assignment method, are susceptible to worst case treatment assignments. Worst case treatment assignments are those admitted by the covariate balance measure, but result in highest possible ATE estimation errors. We developed an adversarial attack to find adversarial treatment assignment for any given trial. Then, we provide an index to measure how close the given trial is to the worst case. To this end, we provide an optimization-based algorithm, namely adversarial treatment assignment in treatment effect trials (ATASTREET), to find the adversarial treatment assignments.

Is overparameterization a privacy liability? In this work, we study the effect that the number of parameters has on a classifier’s vulnerability to membership inference attacks. We first demonstrate how the number of parameters of a model can induce a privacy-utility trade-off: increasing the number of parameters generally improves generalization performance at the expense of lower privacy. However, remarkably, we then show that if coupled with proper regularization, increasing the number of parameters of a model can actually simultaneously increase both its privacy and performance, thereby eliminating the privacy-utility trade-off. Theoretically, we demonstrate this curious phenomenon for logistic regression with ridge regularization in a bi-level feature ensemble setting. Pursuant to our theoretical exploration, we develop a novel leave-one-out analysis tool to precisely characterize the vulnerability of a linear classifier to the optimal membership inference attack. We empirically exhibit this “blessing of dimensionality” for neural networks on a variety of tasks using early stopping as the regularizer

Current Deep Network (DN) visualization and inter-pretability methods rely heavily on data space visualizations such as scoring which dimensions of the data are responsible for their associated prediction or generating new data features or samples that best match a given DN unit or representation. In this paper, we go one step further by developing the first provably exact method for computing the geometry of a DN's mapping - including its decision boundary - over a specified region of the data space. By lever-aging the theory of Continuous Piece- Wise Linear (CPWL) spline DNs, SplineCam exactly computes a DN's geometry without resorting to approximations such as sampling or architecture simplification. SplineCam applies to any DN architecture based on CPWL activation nonlinearities, including (leaky) ReLU, absolute value, maxout, and max-pooling and can also be applied to regression DNs such as implicit neural representations. Beyond decision boundary visualization and characterization, SplineCam enables one to compare architectures, measure generalizability, and sample from the decision boundary on or off the data manifold. Project website: bit.ly/splinecam.

Implicit neural representations (INRs) have recently advanced numerous vision-related areas. INR performance depends strongly on the choice of activation function employed in its MLP network. A wide range of nonlinearities have been explored, but, unfortunately, current INRs designed to have high accuracy also suffer from poor robustness (to signal noise, parameter variation, etc.). Inspired by harmonic analysis, we develop a new, highly accurate and robust INR that does not exhibit this trade off. Our Wavelet Implicit neural REpresentation (WIRE) uses as its activation function the complex Gabor wavelet that is well-known to be optimally concentrated in space-frequency and to have excellent biases for representing images. A wide range of experiments (image denoising, image inpainting, super-resolution, computed tomography reconstruction, image over fitting, and novel view synthesis with neural radiance fields) demonstrate that WIRE defines the new state of the art in INR accuracy, training time, and robustness.

Pairwise dot product-based self-attention is key to the success of transformers which achieve state-of-the-art performance across a variety of applications in language and vision, but are costly to compute. It has been shown that most attention scores and keys in transformers are redundant and can be removed without loss of accuracy. In this paper, we develop a novel probabilistic framework for pruning attention scores and keys in transformers. We first formulate an admixture model of attention keys whose input data to be clustered are attention queries. We show that attention scores in self-attention correspond to the posterior distribution of this model when attention keys admit a uniform prior distribution. We then relax this uniform prior constraint and let the model learn these priors from data, resulting in a new Finite Admixture of Keys (FiAK). The learned priors are used for pruning away redundant attention scores and keys in the baseline transformers, improving the diversity of attention patterns that the models capture. We corroborate the efficiency of transformers pruned with FiAK on the ImageNet object classification and WikiText-103 language modeling tasks. Our experiments demonstrate that transformers pruned with FiAK yield similar or better accuracy than the baseline dense transformers while being much more efficient in terms of memory and computational cost.

Greater financial literacy is critically needed among young adults in the United States [10,35], but many financial literacy education courses have been less effective than hoped for by educators and researchers [7,15]. Additionally, many have not been designed around established curricula or learning science principles, rendering findings difficult for researchers to study empirically [6,34]. In order to better understand the psychosocial mechanisms that predict success in improving learner knowledge and behavior, online educational interventions at scale can be an effective path forward. We conducted interviews with subject matter experts and young adult students to explore the highest priority learning objectives for a brief course curriculum to improve the financial literacy of US young adults. We then leveraged our findings from this study and content from our open-source textbooks to develop the first of several brief online learning interventions for deployment on the large-scale OpenStax Kinetic research infrastructure [2]. In this work-in-progress paper, we discuss the next steps in our research agenda, including course content development and deploying this intervention, as well as our broader plans for our future financial literacy education interventions and translating research into practice with our institutional collaborations.

OpenStax Kinetic is an innovative research infrastructure that aims to transform education and learning research in the digital age. With its access to large sample sizes, authentic learning environments, experimental control, scalability, security and privacy protection, Kinetic provides an unparalleled opportunity for researchers to study the complex interactions between different factors in digital learning environments. This versatile platform utilizes Qualtrics and can support various research designs, including correlational, longitudinal, and interventional studies. Kinetic's unique privacy-by-design implementation via secure enclaves ensures that researchers can analyze fully-identified data without compromising data security and privacy as well as affords greater analytical reproducibility. The findings from Kinetic can inform educational interventions and strategies to enhance student success in digital learning environments. Kinetic has the potential to significantly advance education and learning research by improving pedagogies, practices, and policies in education and learning sciences. In this demo of Kinetic, researchers will be able to interact with the test instance of the Kinetic system online and view the learner experience. All researchers will be able to engage in the experience of creating a study, releasing a study, and interacting with our implementation of secure enclaves for data analysis.

Transformers have achieved remarkable success in a wide range of natural language processing and computer vision applications. However, the representation capacity of a deep transformer model is degraded due to the over-smoothing issue in which the token representations become identical when the model's depth grows. In this work, we show that self-attention layers in transformers minimize a functional which promotes smoothness, thereby causing token uniformity. We then propose a novel regularizer that penalizes the norm of the difference between the smooth output tokens from self-attention and the input tokens to preserve the fidelity of the tokens. Minimizing the resulting regularized energy functional, we derive the Neural Transformer with a Regularized Nonlocal Functional (NeuTRENO), a novel class of transformer models that can mitigate the over-smoothing issue. We empirically demonstrate the advantages of NeuTRENO over the baseline transformers and state-of-the-art methods in reducing the over-smoothing of token representations on various practical tasks, including object classification, image segmentation, and language modeling.

We develop a measure for evaluating the performance of generative networks given two sets of images. A popular performance measure currently used to do this is the Fréchet Inception Distance (FID). FID assumes that images featurized using the penultimate layer of Inception-v3 follow a Gaussian distribution, an assumption which cannot be violated if we wish to use FID as a metric. However, we show that Inception-v3 features of the ImageNet dataset are not Gaussian; in particular, every single marginal is not Gaussian. To remedy this problem, we model the featurized images using Gaussian mixture models (GMMs) and compute the 2-Wasserstein distance restricted to GMMs. We define a performance measure, which we call WaM, on two sets of images by using Inception-v3 (or another classifier) to featurize the images, estimate two GMMs, and use the restricted 2-Wasserstein distance to compare the GMMs. We experimentally show the advantages of WaM over FID, including how FID is more sensitive than WaM to imperceptible image perturbations. By modelling the non-Gaussian features obtained from Inception-v3 as GMMs and using a GMM metric, we can more accurately evaluate generative network performance.

We present Polarity Sampling, a theoretically justified plug-and-play method for controlling the generation quality and diversity of any pre-trained deep generative network (DGN). Leveraging the fact that DGNs are, or can be ap-proximated by, continuous piecewise affine splines, we derive the analytical DGN output space distribution as a function of the product of the DGN's Jacobian singular values raised to a power p. We dub p the polarity param-eter and prove that p focuses the DGN sampling on the modes (p0) of the DGN output-space probability distribution. We demonstrate that nonzero polarity values achieve a better precision-recall (quality-diversity) Pareto frontier than standard methods, such as truncation, for a number of state-of-the-art DGNs. We also present quantitative and qualitative results on the improve-ment of overall generation quality (e.g., in terms of the Fréchet Inception Distance) for a number of state-of-the-art DGNs, including StyleGAN3, BigGAN-deep, NVAE, for different conditional and unconditional image generation tasks. In particular, Polarity Sampling redefines the state-of-the-art for StyleGAN2 on the FFHQ Dataset to FID 2.57, StyleGAN2 on the LSUN Car Dataset to FID 2.27 and Style-GAN3 on the AFHQv2 Dataset to FID 3.95. Colab Demo.

We discuss methods for visualizing neural network decision boundaries and decision regions. We use these visual-izations to investigate issues related to reproducibility and generalization in neural network training. We observe that changes in model architecture (and its associate inductive bias) cause visible changes in decision boundaries, while multiple runs with the same architecture yield results with strong similarities, especially in the case of wide architectures. We also use decision boundary methods to visualize double descent phenomena. We see that decision boundary reproducibility depends strongly on model width. Near the threshold of interpolation, neural network decision bound-aries become fragmented into many small decision regions, and these regions are non-reproducible. Meanwhile, very narrows and very wide networks have high levels of re-producibility in their decision boundaries with relatively few decision regions. We discuss how our observations re-late to the theory of double descent phenomena in convex models. Code is available at https://github.com/somepago/dbViz.

In education applications, knowledge tracing refers to the problem of estimating students' time-varying concept/skill mastery level from their past responses to questions and predicting their future performance.One key limitation of most existing knowledge tracing methods is that they treat student responses to questions as binary-valued, i.e., whether they are correct or incorrect.Response correctness analysis/prediction ignores important information on student knowledge contained in the exact content of the responses, especially for open-ended questions.In this paper, we conduct the first exploration into open-ended knowledge tracing (OKT) by studying the new task of predicting students' exact open-ended responses to questions.Our work is grounded in the domain of computer science education with programming questions.We develop an initial solution to the OKT problem, a student knowledge-guided code generation approach, that combines program synthesis methods using language models with student knowledge tracing methods.We also conduct a series of quantitative and qualitative experiments on a real-world student code dataset to validate OKT and demonstrate its promise in educational applications.

Deep neural networks have become essential for numerous applications due to their strong empirical performance such as vision, RL, and classification. Unfortunately, these networks are quite difficult to interpret, and this limits their applicability in settings where interpretability is important for safety, such as medical imaging. One type of deep neural network is neural tangent kernel that is similar to a kernel machine that provides some aspect of interpretability. To further contribute interpretability with respect to classification and the layers, we develop a new network as a combination of multiple neural tangent kernels, one to model each layer of the deep neural network individually as opposed to past work which attempts to represent the entire network via a single neural tangent kernel. We demonstrate the interpretability of this model on two datasets, showing that the multiple kernels model elucidates the interplay between the layers and predictions.

Computing or approximating the convex hull of a dataset plays a role in a wide range of applications, including economics, statistics, and physics, to name just a few. However, convex hull computation and approximation is exponentially complex, in terms of both memory and computation, as the ambient space dimension increases. In this paper, we propose DeepHull, a new convex hull approximation algorithm based on convex deep networks (DNs) with continuous piecewise-affine nonlinearities and nonnegative weights. The idea is that binary classification between true data samples and adversarially generated samples with such a DN naturally induces a polytope decision boundary that approximates the true data convex hull. A range of exploratory experiments demonstrates that DeepHull efficiently produces a meaningful convex hull approximation, even in a high-dimensional ambient space.

Particle filtering is used to compute nonlinear estimates of complex systems. It samples trajectories from a chosen distribution and computes the estimate as a weighted average of them. Easy-to-sample distributions often lead to degenerate samples where only one trajectory carries all the weight, negatively affecting the resulting performance of the estimate. While much research has been done on the design of appropriate sampling distributions that would lead to controlled degeneracy, in this paper our objective is to learn sampling distributions. Leveraging the framework of algorithm unrolling, we model the sampling distribution as a multivariate normal, and we use neural networks to learn both the mean and the covariance. We carry out unsupervised training of the model to minimize weight degeneracy, relying only on the observed measurements of the system. We show in simulations that the resulting particle filter yields good estimates in a wide range of scenarios.

Centroid based clustering methods such as k-means, k-medoids and k-centers are heavily applied as a go-to tool in exploratory data analysis. In many cases, those methods are used to obtain representative centroids of the data manifold for visualization or summarization of a dataset. Real world datasets often contain inherent abnormalities, e.g., repeated samples and sampling bias, that manifest imbalanced clustering. We propose to remedy such a scenario by introducing a maximal radius constraint r on the clusters formed by the centroids, i.e., samples from the same cluster should not be more than 2r apart in terms of ℓ2distance. We achieve this constraint by solving a semi-definite program, followed by a linear assignment problem with quadratic constraints. Through qualitative results, we show that our proposed method is robust towards dataset imbalances and sampling artifacts. To the best of our knowledge, ours is the first constrained k-means clustering method with hard radius constraints.1

Multi-head attention is a driving force behind state-of-the-art transformers, which achieve remarkable performance across a variety of natural language processing (NLP) and computer vision tasks. It has been observed that for many applications, those attention heads learn redundant embedding, and most of them can be removed without degrading the performance of the model. Inspired by this observation, we propose Transformer with a Mixture of Gaussian Keys (Transformer-MGK), a novel transformer architecture that replaces redundant heads in transformers with a mixture of keys at each head. These mixtures of keys follow a Gaussian mixture model and allow each attention head to focus on different parts of the input sequence efficiently. Compared to its conventional transformer counterpart, Transformer-MGK accelerates training and inference, has fewer parameters, and requires fewer FLOPs to compute while achieving comparable or better accuracy across tasks. Transformer-MGK can also be easily extended to use with linear attention. We empirically demonstrate the advantage of Transformer-MGK in a range of practical applications, including language modeling and tasks that involve very long sequences. On the Wikitext-103 and Long Range Arena benchmark, Transformer-MGKs with 4 heads attain comparable or better performance to the baseline transformers with 8 heads.

Learning engineering adds tools and processes to learning platforms to support improvement research. One kind of tool is A/B testing, which is common in large software companies and also represented academically at conferences like the Annual Conference on Digital Experimentation (CODE). A number of A/B testing systems focused on educational applications have arisen recently, including UpGrade and E-TRIALS. A/B testing can be part of the puzzle of how to improve educational platforms, and yet challenging issues in education go beyond the generic paradigm. For example, the importance of teachers and instructors to learning means that students are not only connecting with software as individuals, but also as part of a shared classroom experience. Further, learning in topics like mathematics can be highly dependent on prior learning, and thus A or B may not be better overall, but only in interaction with prior knowledge. In response, a set of learning platforms is opening their systems to improvement research by instructors and/or third-party researchers, with specific supports necessary for education-specific research designs. This workshop will explore how A/B testing in educational contexts is different, how learning platforms are opening up new possibilities, and how these empirical approaches can be used to drive powerful gains in student learning. It will also discuss forthcoming opportunities for funding to conduct platform-enabled learning research.

A surprising phenomenon in modern machine learning is the ability of a highly overparameterized model to generalize well (small error on the test data) even when it is trained to memorize the training data (zero error on the training data). This has led to an arms race towards increasingly overparameterized models (c.f., deep learning). In this paper, we study an underexplored hidden cost of overparameterization: the fact that overparameterized models may be more vulnerable to privacy attacks, in particular the membership inference attack that predicts the (potentially sensitive) examples used to train a model. We significantly extend the relatively few empirical results on this problem by theoretically proving for an overparameterized linear regression model in the Gaussian data setting that membership inference vulnerability increases with the number of parameters. Moreover, a range of empirical studies indicates that more complex, nonlinear models exhibit the same behavior. Finally, we extend our analysis towards ridge-regularized linear regression and show in the Gaussian data setting that increased regularization also increases membership inference vulnerability in the overparameterized regime.

Inferring appropriate information from large datasets has become important. In particular, identifying relationships among variables in these datasets has far-reaching impacts. In this article, we introduce the uniform information coefficient (UIC), which measures the amount of dependence between two multidimensional variables and is able to detect both linear and non-linear associations. Our proposed UIC is inspired by the maximal information coefficient (MIC) [1].; however, the MIC was originally designed to measure dependence between two one-dimensional variables. Unlike the MIC calculation that depends on the type of association between two variables, we show that the UIC calculation is less computationally expensive and more robust to the type of association between two variables. The UIC achieves this by replacing the dynamic programming step in the MIC calculation with a simpler technique based on the uniform partitioning of the data grid. This computational efficiency comes at the cost of not maximizing the information coefficient as done by the MIC algorithm. We present theoretical guarantees for the performance of the UIC and a variety of experiments to demonstrate its quality in detecting associations.

Stochastic gradient descent (SGD) algorithms, with constant momentum and its variants such as Adam, are the optimization methods of choice for training deep neural networks (DNNs). There is great interest in speeding up the convergence of these methods due to their high computational expense. Nesterov accelerated gradient with a time-varying momentum (NAG) improves the convergence rate of gradient descent for convex optimization using a specially designed momentum; however, it accumulates error when the stochastic gradient is used, slowing convergence at best and diverging at worst. In this paper, we propose scheduled restart SGD (SRSGD), a new NAG-style scheme for training DNNs. SRSGD replaces the constant momentum in SGD by the increasing momentum in NAG but stabilizes the iterations by resetting the momentum to zero according to a schedule. Using a variety of models and benchmarks for image classification, we demonstrate that, in training DNNs, SRSGD significantly improves convergence and generalization; for instance, in training ResNet-200 for ImageNet classification, SRSGD achieves an error rate of 20.93% versus the benchmark of 22.13%. These improvements become more significant as the network grows deeper. Furthermore, on both CIFAR and ImageNet, SRSGD reaches similar or even better error rates with significantly fewer training epochs compared to the SGD baseline. Our implementation of SRSGD is available at https://github.com/minhtannguyen/SRSGD.

We introduce an end-to-end (E2E) deep neural network architecture designed to perform seismo-volcanic monitoring focused on detecting change. Due to the complexity of volcanic processes, this requires a polyphonic detection, segmentation, and classification approach. Through evolving epistemic uncertainty, invoking a Bayesian network strategy, we detect change and demonstrate its significance as an indicator for possible forecasting of eruptions using data from the Bezymianny and Etna volcanoes. Specifically, we propose morphing the scattering transform from previous work into a novel E2E hybrid and recurrent learnable deep scattering network to adapt to multi-scale temporal dependencies from streaming data. The time-dependent scattering is in some sense physics informed, namely, through time–frequency representation (TFR) of the data. At the same time, with a carefully designed deep convolutional LSTM (ConvLSTM) architecture, we learn intra-event, temporal dynamics from the scattering coefficients or features. We verify the effectiveness of transfer learning switching between volcanoes. Our experimental results set a new norm for semi-supervised seismo-volcanic monitoring.

Online education platforms enable teachers to share a large number of educational resources such as questions to form exercises and quizzes for students. With large volumes of available questions, it is important to have an automated way to quantify their properties and intelligently select them for students, enabling effective and personalized learning experiences. In this work, we propose a framework for mining insights from educational questions at scale. We utilize the state-of-the-art Bayesian deep learning method, in particular partial variational auto-encoders (p-VAE), to analyze real students' answers to a large collection of questions. Based on p-VAE, we propose two novel metrics that quantify question quality and difficulty, respectively, and a personalized strategy to adaptively select questions for students. We apply our proposed framework to a real-world dataset with tens of thousands of questions and tens of millions of answers from an online education platform. Our framework not only demonstrates promising results in terms of statistical metrics but also obtains highly consistent results with domain experts' evaluation.

Exploiting the ever-growing corpus of scientific content calls for new ways and means to effectively organize, search, and retrieve scientific formulae. We propose a new data-driven framework for retrieving similar scientific formulae via learned formula representations based on tree embeddings. FORTE (for FOrmula Representation learning via Tree Embeddings) leverages operator tree representations of symbolic scientific formulae (such as math equations) to explicitly capture their inherent structural and semantic properties. FORTE employs i) a tree encoder that encodes the formula’s operator tree into an embedding vector and ii) a tree decoder that directly generates a formula’s operator tree from the embedding vector. We also develop a novel tree beam search algorithm that improves the quality of the decoded operator trees. We demonstrate that FORTE (sometimes significantly) outperforms various baseline methods on formula reconstruction and retrieval using a real-world dataset comprising 770k scientific formulae collected on-line.

We study the problem of generating arithmetic math word problems (MWPs) given a math equation that specifies the mathematical computation and a context that specifies the problem scenario.Existing approaches are prone to generating MWPs that are either mathematically invalid or have unsatisfactory language quality.They also either ignore the context or require manual specification of a problem template, which compromises the diversity of the generated MWPs.In this paper, we develop a novel MWP generation approach that leverages i) pre-trained language models and a context keyword selection model to improve the language quality of the generated MWPs and ii) an equation consistency constraint for math equations to improve the mathematical validity of the generated MWPs.Extensive quantitative and qualitative experiments on three realworld MWP datasets demonstrate the superior performance of our approach compared to various baselines.

High dimensionality poses many challenges to the use of data, from visualization and interpretation, to prediction and storage for historical preservation. Techniques abound to reduce the dimensionality of fixed-length sequences, yet these methods rarely generalize to variable-length sequences. To address this gap, we extend existing methods that rely on the use of kernels to variable-length sequences via use of the Recurrent Neural Tangent Kernel (RNTK). Since a deep neural network with ReLu activation is a Max-Affine Spline Operator (MASO), we dub our approach Max-Affine Spline Kernel (MASK). We demonstrate how MASK can be used to extend principal components analysis (PCA) and t-distributed stochastic neighbor embedding (t-SNE) and apply these new algorithms to separate synthetic time series data sampled from second-order differential equations.

Among the most successful methods for sparsifying deep (neural) networks are those that adaptively mask the network weights throughout training. By examining this masking, or dropout, in the linear case, we uncover a duality between such adaptive methods and regularization through the so-called “η-trick” that casts both as iteratively reweighted optimizations. We show that any dropout strategy that adapts to the weights in a monotonic way corresponds to an effective subquadratic regularization penalty, and therefore leads to sparse solutions. We obtain the effective penalties for several popular sparsification strategies, which are remarkably similar to classical penalties commonly used in sparse optimization. Considering variational dropout as a case study, we demonstrate similar empirical behavior between the adaptive dropout method and classical methods on the task of deep network sparsification, validating our theory.

We introduce a novel video-rate hyperspectral imager with high spatial, temporal and spectral resolutions. Our key hypothesis is that spectral profiles of pixels within each super-pixel tend to be similar. Hence, a scene-adaptive spatial sampling of a hyperspectral scene, guided by its super-pixel segmented image, is capable of obtaining high-quality reconstructions. To achieve this, we acquire an RGB image of the scene, compute its super-pixels, from which we generate a spatial mask of locations where we measure high-resolution spectrum. The hyperspectral image is subsequently estimated by fusing the RGB image and the spectral measurements using a learnable guided filtering approach. Due to low computational complexity of the superpixel estimation step, our setup can capture hyperspectral images of the scenes with little overhead over traditional snapshot hyperspectral cameras, but with significantly higher spatial and spectral resolutions. We validate the proposed technique with extensive simulations as well as a lab prototype that measures hyperspectral video at a spatial resolution of 600 ×900 pixels, at a spectral resolution of 10 nm over visible wavebands, and achieving a frame rate at 18fps.

We build a rigorous bridge between deep networks (DNs) and approximation theory via spline functions and operators. Our key result is that a large class of DNs can be written as a composition of max-affine spline operators (MASOs) that provide a powerful portal through which we view and analyze their inner workings. For instance, conditioned on the spline partition region containing the input signal, the output of an MASO DN can be written as a simple affine transformation of the input. This implies that a DN constructs a set of signal-dependent, class-specific templates against which the signal is compared via a simple inner product; we explore the links to the classical theory of optimal classification via matched filters and the effects of data memorization. Going further, we propose a simple penalty term that can be added to the cost function of any DN learning algorithm to force the templates to be orthogonal with each other; this leads to significantly improved classification performance and reduced overfitting with no change to the DN architecture. The spline partition of the input signal space that is implicitly induced by an MASO directly links DNs to the theory of vector quantization (VQ) and K-means clustering, which opens up new geometric avenues to study how DNs organize signals in a hierarchical fashion. To validate the utility of the VQ interpretation, we develop and validate a new distance metric for signals and images that quantify the difference between their VQ encodings.

In this paper, we introduce a new online decision making paradigm that we call Thresholding Graph Bandits. The main goal is to efficiently identify a subset of arms in a multi-armed bandit problem whose means are above a specified threshold. While traditionally in such problems, the arms are assumed to be independent, in our paradigm we further suppose that we have access to the similarity between the arms in the form of a graph, allowing us to gain information about the arm means with fewer samples. Such a feature is particularly relevant in modern decision making problems, where rapid decisions need to be made in spite of the large number of options available. We present GrAPL, a novel algorithm for the thresholding graph bandit problem. We demonstrate theoretically that this algorithm is effective in taking advantage of the graph structure when the structure is reflective of the distribution of the rewards. We confirm these theoretical findings via experiments on both synthetic and real data.

Ensemble methods that average over a collection of independent predictors that are each limited to a subsampling of both the examples and features of the training data command a significant presence in machine learning, such as the ever-popular random forest, yet the nature of the subsampling effect, particularly of the features, is not well understood. We study the case of an ensemble of linear predictors, where each individual predictor is fit using ordinary least squares on a random submatrix of the data matrix. We show that, under standard Gaussianity assumptions, when the number of features selected for each predictor is optimally tuned, the asymptotic risk of a large ensemble is equal to the asymptotic ridge regression risk, which is known to be optimal among linear predictors in this setting. In addition to eliciting this implicit regularization that results from subsampling, we also connect this ensemble to the dropout technique used in training deep (neural) networks, another strategy that has been shown to have a ridge-like regularizing effect.

Word embedding models learn semantically rich vector representations of words and are widely used to initialize natural processing language (NLP) models.The popular continuous bag-ofwords (CBOW) model of word2vec learns a vector embedding by masking a given word in a sentence and then using the other words as a context to predict it.A limitation of CBOW is that it equally weights the context words when making a prediction, which is inefficient, since some words have higher predictive value than others.We tackle this inefficiency by introducing the Attention Word Embedding (AWE) model, which integrates the attention mechanism into the CBOW model.We also propose AWE-S, which incorporates subword information.We demonstrate that AWE and AWE-S outperform the state-of-the-art word embedding models both on a variety of word similarity datasets and when used for initialization of NLP models.

The standard pipeline for many vision tasks uses a conventional camera to capture an image that is then passed to a digital processor for information extraction. In some deployments, such as private locations, the captured digital imagery contains sensitive information exposed to digital vulnerabilities such as spyware, Trojans, etc. However, in many applications, the full imagery is unnecessary for the vision task at hand. In this paper we propose an optical and analog system that preprocesses the light from the scene before it reaches the digital imager to destroy sensitive information. We explore analog and optical encodings consisting of easily implementable operations such as convolution, pooling, and quantization. We perform a case study to evaluate how such encodings can destroy face identity information while preserving enough information for face detection. The encoding parameters are learned via an alternating optimization scheme based on adversarial learning with deep neural networks. We name our system CAnOPIC (Camera with Analog and Optical Privacy-Integrating Computations) and show that it has better performance in terms of both privacy and utility than conventional optical privacy-enhancing methods such as blurring and pixelation.

We present the first sublinear memory sketch that can be queried to find the nearest neighbors in a dataset. Our online sketching algorithm compresses an N element dataset to a sketch of size $O(N^b \log^3 N)$ in $O(N^{(b+1)} \log^3 N)$ time, where $b < 1$. This sketch can correctly report the nearest neighbors of any query that satisfies a stability condition parameterized by $b$. We achieve sublinear memory performance on stable queries by combining recent advances in locality sensitive hash (LSH)-based estimators, online kernel density estimation, and compressed sensing. Our theoretical results shed new light on the memory-accuracy tradeoff for nearest neighbor search, and our sketch, which consists entirely of short integer arrays, has a variety of attractive features in practice. We evaluate the memory-recall tradeoff of our method on a friend recommendation task in the Google plus social media network. We obtain orders of magnitude better compression than the random projection based alternative while retaining the ability to report the nearest neighbors of practical queries.

We study the linear subspace fitting problem in the overparameterized setting, where the estimated subspace can perfectly interpolate the training examples. Our scope includes the least-squares solutions to subspace fitting tasks with varying levels of supervision in the training data (i.e., the proportion of input-output examples of the desired low-dimensional mapping) and orthonormality of the vectors defining the learned operator. This flexible family of problems connects standard, unsupervised subspace fitting that enforces strict orthonormality with a corresponding regression task that is fully supervised and does not constrain the linear operator structure. This class of problems is defined over a supervision-orthonormality plane, where each coordinate induces a problem instance with a unique pair of supervision level and softness of orthonormality constraints. We explore this plane and show that the generalization errors of the corresponding subspace fitting problems follow double descent trends as the settings become more supervised and less orthonormally constrained.

Deep Generative Networks (DGNs) with probabilistic modeling of their output and latent space are currently trained via Variational Autoencoders (VAEs). In the absence of a known analytical form for the posterior and likelihood expectation, VAEs resort to approximations, including (Amortized) Variational Inference (AVI) and Monte-Carlo sampling. We exploit the Continuous Piecewise Affine property of modern DGNs to derive their posterior and marginal distributions as well as the latter's first two moments. These findings enable us to derive an analytical Expectation-Maximization (EM) algorithm for gradient-free DGN learning. We demonstrate empirically that EM training of DGNs produces greater likelihood than VAE training. Our new framework will guide the design of new VAE AVI that better approximates the true posterior and open new avenues to apply standard statistical tools for model comparison, anomaly detection, and missing data imputation.

Designing deep neural networks is an art that often involves an expensive search over candidate architectures. To overcome this for recurrent neural nets (RNNs), we establish a connection between the hidden state dynamics in an RNN and gradient descent (GD). We then integrate momentum into this framework and propose a new family of RNNs, called {\em MomentumRNNs}. We theoretically prove and numerically demonstrate that MomentumRNNs alleviate the vanishing gradient issue in training RNNs. We study the momentum long-short term memory (MomentumLSTM) and verify its advantages in convergence speed and accuracy over its LSTM counterpart across a variety of benchmarks. We also demonstrate that MomentumRNN is applicable to many types of recurrent cells, including those in the state-of-the-art orthogonal RNNs. Finally, we show that other advanced momentum-based optimization methods, such as Adam and Nesterov accelerated gradients with a restart, can be easily incorporated into the MomentumRNN framework for designing new recurrent cells with even better performance.

We provide the first frame agnostic thresholding scheme based on risk minimization, which can be applied to arbitrary frames and provide its theoretical guarantees. We investigate the proposed scheme, study its empirical risk, and demonstrates how it falls back to the standard Donoho thresholding scheme for orthogonal basis. We then validate our technique and apply it to the overcomplete wavelet transforms of the Deep Scattering Network. We are thus obtaining an invariant and thresholded representation of the signals providing significant performance gains compared to the non-thresholded version.

Algorithms often carry out equally many computations for "easy" and "hard" problem instances. In particular, algorithms for finding nearest neighbors typically have the same running time regardless of the particular problem instance. In this paper, we consider the approximate $k$-nearest-neighbor problem, which is the problem of finding a subset of O(k) points in a given set of points that contains the set of $k$ nearest neighbors of a given query point. We propose an algorithm based on adaptively estimating the distances, and show that it is essentially optimal out of algorithms that are only allowed to adaptively estimate distances. We then demonstrate both theoretically and experimentally that the algorithm can achieve significant speedups relative to the naive method.

The 2016 United States presidential election has been characterized as a period of extreme divisiveness that was exacerbated on social media by the influence of fake news, trolls, and social bots. However, the extent to which the public became more polarized in response to these influences over the course of the election is not well understood. In this paper we propose IdeoTrace, a framework for (i) jointly estimating the ideology of social media users and news websites and (ii) tracing changes in user ideology over time. We apply this framework to the last two months of the election period for a group of 47508 Twitter users and demonstrate that both liberal and conservative users became more polarized over time.

We study the geometry of deep (neural) networks (DNs) with piecewise affine and convex nonlinearities. The layers of such DNs have been shown to be max-affine spline operators (MASOs) that partition their input space and apply a region-dependent affine mapping to their input to produce their output. We demonstrate that each MASO layer's input space partitioning corresponds to a power diagram (an extension of the classical Voronoi tiling) with a number of regions that grows exponentially with respect to the number of units (neurons). We further show that a composition of MASO layers (e.g., the entire DN) produces a progressively subdivided power diagram and provide its analytical form. The subdivision process constrains the affine maps on the potentially exponentially many power diagram regions with respect to the number of neurons to greatly reduce their complexity. For classification problems, we obtain a formula for a MASO DN's decision boundary in the input space plus a measure of its curvature that depends on the DN's nonlinearities, weights, and architecture. Numerous numerical experiments support and extend our theoretical results.

In our daily lives, we rely heavily on our visual and auditory channels to receive information from others. In the case of impairment, or when large amounts of information are already transmitted visually or aurally, alternative methods of communication are needed. A haptic language offers the potential to provide information to a user when visual and auditory channels are unavailable. Previously created haptic languages include deconstructing acoustic signals into features and displaying them through a haptic device, and haptic adaptations of Braille or Morse code; however, these approaches are unintuitive, slow at presenting language, or require a large surface area. We propose using a multi-sensory haptic device called MISSIVE, which can be worn on the upper arm and is capable of producing brief cues, sufficient in quantity to encode the full English phoneme set. We evaluated our approach by teaching subjects a subset of 23 phonemes, and demonstrated an 86% accuracy in a 50 word identification task after 100 minutes of training.

Sensor selection refers to the problem of intelligently selecting a small subset of a collection of available sensors to reduce the sensing cost while preserving signal acquisition performance. The majority of sensor selection algorithms find the subset of sensors that best recovers an arbitrary signal from a number of linear measurements that is larger than the dimension of the signal. In this paper, we develop a new sensor selection algorithm for sparse (or near sparse) signals that finds a subset of sensors that best recovers such signals from a number of measurements that is much smaller than the dimension of the signal. Existing sensor selection algorithms cannot be applied in such situations. Our proposed Incoherent Sensor Selection (Insense) algorithm minimizes a coherence-based cost function that is adapted from recent results in sparse recovery theory. Using three datasets, including a real-world dataset on microbial diagnostics, we demonstrate the superior performance of Insense for sparse-signal sensor selection.

Feature selection is an important challenge in machine learning. It plays a crucial role in the explainability of machine-driven decisions that are rapidly permeating throughout modern society. Unfortunately, the explosion in the size and dimensionality of real-world datasets poses a severe challenge to standard feature selection algorithms. Today, it is not uncommon for datasets to have billions of dimensions. At such scale, even storing the feature vector is impossible, causing most existing feature selection methods to fail. Workarounds like feature hashing, a standard approach to large-scale machine learning, helps with the computational feasibility, but at the cost of losing the interpretability of features. In this paper, we present MISSION, a novel framework for ultra large-scale feature selection that performs stochastic gradient descent while maintaining an efficient representation of the features in memory using a Count-Sketch data structure. MISSION retains the simplicity of feature hashing without sacrificing the interpretability of the features while using only O(log^2(p)) working memory. We demonstrate that MISSION accurately and efficiently performs feature selection on real-world, large-scale datasets with billions of dimensions.

We propose to tackle the problem of end-to-end learning for raw waveform signals by introducing learnable continuous time-frequency atoms. The derivation of these filters is achieved by defining a functional space with a given smoothness order and boundary conditions. From this space, we derive the parametric analytical filters. Their differentiability property allows gradient-based optimization. As such, one can utilize any Deep Neural Network (DNN) with these filters. This enables us to tackle in a front-end fashion a large scale bird detection task based on the freefield1010 dataset known to contain key challenges, such as the dimensionality of the inputs data ($>100,000$) and the presence of additional noises: multiple sources and soundscapes.

Phase retrieval algorithms have become an important component in many modern computational imaging systems. For instance, in the context of ptychography and speckle correlation imaging, they enable imaging past the diffraction limit and through scattering media, respectively. Unfortunately, traditional phase retrieval algorithms struggle in the presence of noise. Progress has been made recently on developing more robust algorithms using signal priors, but at the expense of limiting the range of supported measurement models (e.g., to Gaussian or coded diffraction patterns). In this work we leverage the regularization-by-denoising framework and a convolutional neural network denoiser to create prDeep, a new phase retrieval algorithm that is both robust and broadly applicable. We test and validate prDeep in simulation to demonstrate that it is robust to noise and can handle a variety of system models.

The ever growing amount of educational content renders it increasingly difficult to manually generate sufficient practice or quiz questions to accompany it. This paper introduces QG-Net, a recurrent neural network-based model specifically designed for automatically generating quiz questions from educational content such as textbooks. QG-Net, when trained on a publicly available, general-purpose question/answer dataset and without further fine-tuning, is capable of generating high quality questions from textbooks, where the content is significantly different from the training data. Indeed, QG-Net outperforms state-of-the-art neural network-based and rules-based systems for question generation, both when evaluated using standard benchmark datasets and when using human evaluators. QG-Net also scales favorably to applications with large amounts of educational content, since its performance improves with the amount of training data.

This paper introduces RankMap, a platform-aware end-to-end framework for efficient execution of a broad class of iterative learning algorithms for massive and dense data sets. Our framework exploits data structure to scalably factorize it into an ensemble of lower rank subspaces. The factorization creates sparse low-dimensional representations of the data, a property which is leveraged to devise effective mapping and scheduling of iterative learning algorithms on the distributed computing machines. We provide two APIs, one matrix-based and one graph-based, which facilitate automated adoption of the framework for performing several contemporary learning applications. To demonstrate the utility of RankMap, we solve sparse recovery and power iteration problems on various real-world data sets with up to 1.8 billion nonzeros. Our evaluations are performed on Amazon EC2 and IBM iDataPlex servers using up to 244 cores. The results demonstrate up to two orders of magnitude improvements in memory usage, execution speed, and bandwidth compared with the best reported prior work, while achieving the same level of learning accuracy.

Optimizing the selection of learning resources and practice questions to address each individual student's needs has the potential to improve students' learning efficiency. In this paper, we study the problem of selecting a personalized learning action for each student (e.g. watching a lecture video, working on a practice question, etc.), based on their prior performance, in order to maximize their learning outcome. We formulate this problem using the contextual multi-armed bandits framework, where students' prior concept knowledge states (estimated from their responses to questions in previous assessments) correspond to contexts, the personalized learning actions correspond to arms, and their performance on future assessments correspond to rewards. We propose three new Bayesian policies to select personalized learning actions for students that each exhibits advantages over prior work, and experimentally validate them using real-world datasets.

The promise of compressive sensing (CS) has been offset by two significant challenges. First, real-world data is not exactly sparse in a fixed basis. Second, current high-performance recovery algorithms are slow to converge, which limits CS to either non-real-time applications or scenarios where massive back-end computing is available. In this paper, we attack both of these challenges head-on by developing a new signal recovery framework we call DeepInverse that learns the inverse transformation from measurement vectors to signals using a deep convolutional network. When trained on a set of representative images, the network learns both a representation for the signals (addressing challenge one) and an inverse map approximating a greedy or convex recovery algorithm (addressing challenge two). Our experiments indicate that the DeepInverse network closely approximates the solution produced by state-of-the-art CS recovery algorithms yet is hundreds of times faster in run time. The tradeoff for the ultrafast run time is a computationally intensive, off-line training procedure typical to deep networks. However, the training needs to be completed only once, which makes the approach attractive for a host of sparse recovery problems.

Lensless imaging systems, such as the recently proposed FlatCam, offer numerous advantages over lens-based systems such as a thin form-factor, low cost, and higher light throughput. However, little work has been done in analyzing these systems' depth of field characteristics. A depth-dependent calibration step is necessary to obtain the image from the FlatCam measurements, and this calibration determines the system's depth of field. In this paper, we characterize the FlatCam's depth of field properties and show that (a) for scene depths on the order of tens of centimeters, it is possible to perform depth-selective refocusing from a single captured image and (b) for sufficiently large scene depths, calibratin.g for one depth can provide a very large depth of field.

A transmission matrix describes the input-output relationship of a complex wavefront as it passes through/reflects off a multiple-scattering medium, such as frosted glass or a painted wall. Knowing a medium's transmission matrix enables one to image through the medium, send signals through the medium, or even use the medium as a lens. The double phase retrieval method is a recently proposed technique to learn a medium's transmission matrix that avoids difficult-to-capture interferometric measurements. Unfortunately, to perform high resolution imaging, existing double phase retrieval methods require (1) a large number of measurements and (2) an unreasonable amount of computation. In this work we focus on the latter of these two problems and reduce computation times with two distinct methods: First, we develop a new phase retrieval algorithm that is significantly faster than existing methods, especially when used with an amplitude-only spatial light modulator (SLM). Second, we calibrate the system using a phase-only SLM, rather than an amplitude-only SLM which was used in previous double phase retrieval experiments. This seemingly trivial change enables us to use a far faster class of phase retrieval algorithms. As a result of these advances, we achieve a 100x reduction in computation times, thereby allowing us to image through scattering media at state-of-the-art resolutions. In addition to these advances, we also release the first publicly available transmission matrix dataset. This contribution will enable phase retrieval researchers to apply their algorithms to real data. Of particular interest to this community, our measurement vectors are naturally i.i.d. subgaussian, i.e., no coded diffraction pattern is required.

Hashing is an important tool in large-scale machine learning. Unfortunately, current data-dependent hashing algorithms are not robust to small perturbations of the data points, which degrades the performance of nearest neighbor (NN) search. The culprit is the minimization of the L_2-norm, average distortion among pairs of points to find the hash function. Inspired by recent progress in robust optimization, we develop a novel hashing algorithm, dubbed RHash, that instead minimizes the L_1-norm, worst-case distortion among pairs of points. We develop practical and efficient implementations of RHash that couple the alternating direction method of multipliers (ADMM) framework with column generation to scale well to large datasets. A range of experimental evaluations demonstrate the superiority of RHash over ten state-of-the-art binary hashing schemes. In particular, we show that RHash achieves the same retrieval performance as the state-of-the-art algorithms in terms of average precision while using up to 60% fewer bits.

Hypothesis testing of covariance matrices is an important problem in multivariate analysis. Given n data samples and a covariance matrix Σ0, the goal is to determine whether or not the data is consistent with this matrix. In this paper we introduce a framework that we call sketched covariance testing, where the data is provided after being compressed by multiplying by a “sketching” matrix A chosen by the analyst. We propose a statistical test in this setting and quantify an achievable sample complexity as a function of the amount of compression. Our result reveals an intriguing achievable tradeoff between the compression ratio and the statistical information required for reliable hypothesis testing; the sample complexity increases as the fourth power of the amount of compression.

An important, yet largely unstudied, problem in student data analysis is to detect misconceptions from students' responses to open-response questions. Misconception detection enables instructors to deliver more targeted feedback on the misconceptions exhibited by many students in their class, thus improving the quality of instruction. In this paper, we propose a new natural language processing (NLP) framework to detect the common misconceptions among students' textual responses to open-response, short-answer questions. We introduce a probabilistic model for students' textual responses involving misconceptions and experimentally validate it on a real-world student-response dataset. Preliminary experimental results show that our proposed framework excels at classifying whether a response exhibits one or more misconceptions. More importantly, it can also automatically detect the common misconceptions exhibited across responses from multiple students to multiple questions; this is especially important at large scale, since instructors will no longer need to manually specify all possible misconceptions that students might exhibit.

Compressive image recovery is a challenging problem that requires fast and accurate algorithms. Recently, neural networks have been applied to this problem with promising results. By exploiting massively parallel GPU processing architectures and oodles of training data, they can run orders of magnitude faster than existing techniques. However, these methods are largely unprincipled black boxes that are difficult to train and often-times specific to a single measurement matrix. It was recently demonstrated that iterative sparse-signal-recovery algorithms can be ``unrolled’' to form interpretable deep networks. Taking inspiration from this work, we develop a novel neural network architecture that mimics the behavior of the denoising-based approximate message passing (D-AMP) algorithm. We call this new network {\em Learned} D-AMP (LDAMP). The LDAMP network is easy to train, can be applied to a variety of different measurement matrices, and comes with a state-evolution heuristic that accurately predicts its performance. Most importantly, it outperforms the state-of-the-art BM3D-AMP and NLR-CS algorithms in terms of both accuracy and run time. At high resolutions, and when used with sensing matrices that have fast implementations, LDAMP runs over $50\times$ faster than BM3D-AMP and hundreds of times faster than NLR-CS.

Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem-for example, in determining the relationship between genetics and the presence or absence of a disease-or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s-sparse signals in Rn can be estimated (up to normalization) from Ω(slog (n/s)) one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor λ := m/(s log(n/s)), where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by Ω(λ-1). Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to e-Ω(λ). This improves upon guarantees for other methods of adaptive thresholding, such as sigma- delta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomial-time algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the one-bit compressed sensing model, in which the engineer controls the measurement procedure, to sigma-delta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression.

The explosion of computational imaging has seen the frontier of image processing move past linear problems, like denoising and deblurring, and towards non-linear problems such as phase retrieval. There has a been a corresponding research thrust into non-linear image recovery algorithms, but in many ways this research is stuck where linear problem research was twenty years ago: Models, if used at all, are simple designs like sparsity or smoothness. In this paper we use denoisers to impose elaborate and accurate models in order to perform inference on generalized linear systems. More specifically, we use the state-of-the-art BM3D denoiser within the Generalized Approximate Message Passing (GAMP) framework to solve compressive phase retrieval in a variety of different contexts. Our method demonstrates recovery performance equivalent to existing techniques using fewer than half as many measurements. This dramatic improvement in compressive phase retrieval performance opens the door for a whole new class of imaging systems.

Statistical models of student responses on assessment questions, such as those in homeworks and exams, enable educators and computer-based personalized learning systems to gain insights into students’ knowledge using machine learning. Popular student-response models, including the Rasch model and item response theory models, represent the probability of a student answering a question correctly using an affine function of latent factors. While such models can accurately predict student responses, their ability to interpret the underlying knowledge structure (which is certainly nonlinear) is limited. In response, we develop a new, nonlinear latent variable model that we call the dealbreaker model, in which a student’s success probability is determined by their weakest concept mastery. We develop efficient parameter inference algorithms for this model using novel methods for nonconvex optimization. We show that the dealbreaker model achieves comparable or better prediction performance as compared to affine models with real-world educational datasets. We further demonstrate that the parameters learned by the dealbreaker model are interpretable—they provide key insights into which concepts are critical (i.e., the “dealbreaker”) to answering a question correctly. We conclude by reporting preliminary results for a movie-rating dataset, which illustrate the broader applicability of the dealbreaker model.

We develop a probabilistic framework for deep learning based on the Deep Rendering Mixture Model (DRMM), a new generative probabilistic model that explicitly capture variations in data due to latent task nuisance variables. We demonstrate that max-sum inference in the DRMM yields an algorithm that exactly reproduces the operations in deep convolutional neural networks (DCNs), providing a first principles derivation. Our framework provides new insights into the successes and shortcomings of DCNs as well as a principled route to their improvement. DRMM training via the Expectation-Maximization (EM) algorithm is a powerful alternative to DCN back-propagation, and initial training results are promising. Classification based on the DRMM and other variants outperforms DCNs in supervised digit classification, training 2-3x faster while achieving similar accuracy. Moreover, the DRMM is applicable to semi-supervised and unsupervised learning tasks, achieving results that are state-of-the-art in several categories on the MNIST benchmark and comparable to state of the art on the CIFAR10 benchmark.

Kernel matrices that encode the distance (or similarity) between data points are widely used throughout the computational sciences for classification, clustering, and dimensionality reduction. For large datasets, the cost of computing and factorizing such matrices becomes intractable. Thus instead of operating on the entire matrix, approximate methods such as the Nyström method and the incomplete Cholesky decomposition (ICD) generate a low rank matrix factorization using only a subset of the matrix columns (or rows). Here, we present an adaptive column sampling strategy for the Nyström method that we dub Accelerated Sequential Incoherence Selection (oASIS). This sampling strategy reveals a missing link between Nyström methods and ICD: we demonstrate that ICD is actually a special case of the Nyström method with the oASIS adaptive sampling rule. Numerical experiments and theoretical results suggest that oASIS achieves performance comparable to state-of-the-art greedy Nyström methods but with shorter runtimes and less memory consumption.

A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, todays denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop an extension of the approximate message passing (AMP) framework, called denoising-based AMP (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high-performance denoiser for natural images, D-AMP offers the state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP is the use of an appropriate Onsager correction term in its iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove.

A denoising algorithm seeks to remove perturbations or errors from a signal. The last three decades have seen extensive research devoted to this arena, and as a result, today's denoisers are highly optimized algorithms that effectively remove large amounts of additive white Gaussian noise. A compressive sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired from a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop a denoising-based approximate message passing (D-AMP) algorithm that is capable of high-performance reconstruction. We demonstrate using the high performance BM3D denoiser that D-AMP offers state-of-the-art CS recovery performance for natural images (on average 9dB better than sparsity-based algorithms), while operating tens of times faster than the only competitive method. A critical insight in our approach is the use of an appropriate Onsager correction term in the D-AMP iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove. On the analytical side, we develop a new state evolution framework for deterministic signals that accurately predicts the performance of D-AMP and enables us to derive several useful theoretical features.

While computer and communication technologies have provided effective means to scale up many aspects of education, the submission and grading of assessments such as homework assignments and tests remains a weak link. In this paper, we study the problem of automatically grading the kinds of open response mathematical questions that figure prominently in STEM (science, technology, engineering, and mathematics) courses. Our data-driven framework for mathematical language processing (MLP) leverages solution data from a large number of learners to evaluate the correctness of their solutions, assign partial-credit scores, and provide feedback to each learner on the likely locations of any errors. MLP takes inspiration from the success of natural language processing for text data and comprises three main steps. First, we convert each solution to an open response mathematical question into a series of numerical features. Second, we cluster the features from several solutions to uncover the structures of correct, partially correct, and incorrect solutions. We develop two different clustering approaches, one that leverages generic clustering algorithms and one based on Bayesian nonparametrics. Third, we automatically grade the remaining (potentially large number of) solutions based on their assigned cluster and one instructor-provided grade per cluster. As a bonus, we can track the cluster assignment of each step of a multistep solution and determine when it departs from a cluster of correct solutions, which enables us to indicate the likely locations of errors to learners. We test and validate MLP on real-world MOOC data to demonstrate how it can substantially reduce the human effort required in large-scale educational platforms.

Advances in online and computer supported education afford exciting opportunities to revolutionize the classroom, while also presenting a number of new challenges not faced in traditional educational settings. Foremost among these challenges is the problem of accurately and efficiently evaluating learner work as the class size grows, which is directly related to the larger goal of providing quality, timely, and actionable formative feedback. Recently there has been a surge in interest in using peer grading methods coupled with machine learning to accurately and fairly evaluate learner work while alleviating the instructor bottleneck and grading overload. Prior work in peer grading almost exclusively focuses on numerically scored grades -- either real-valued or ordinal. In this work, we consider the implications of peer ranking in which learners rank a small subset of peer work from strongest to weakest, and propose new types of computational analyses that can be applied to this ranking data. We adopt a Bayesian approach to the ranked peer grading problem and develop a novel model and method for utilizing ranked peer-grading data. We additionally develop a novel procedure for adaptively identifying which work should be ranked by particular peers in order to dynamically resolve ambiguity in the data and rapidly resolve a clearer picture of learner performance. We showcase our results on both synthetic and several real-world educational datasets.

Spatial multiplexing cameras (SMCs) acquire a (typically static) scene through a series of coded projections using a spatial light modulator (e.g., a digital micromirror device) and a few optical sensors. This approach finds use in imaging applications where full-frame sensors are either too expensive (e.g., for short-wave infrared wavelengths) or unavailable. Existing SMC systems reconstruct static scenes using techniques from compressive sensing (CS). For videos, however, existing acquisition and recovery methods deliver poor quality. In this paper, we propose the CS multiscale video (CS-MUVI) sensing and recovery framework for high-quality video acquisition and recovery using SMCs. Our framework features novel sensing matrices that enable the efficient computation of a low-resolution video preview, while enabling high-resolution video recovery using convex optimization. To further improve the quality of the reconstructed videos, we extract optical-flow estimates from the low-resolution previews and impose them as constraints in the recovery procedure. We demonstrate the efficacy of our CS-MUVI framework for a host of synthetic and real measured SMC video data, and we show that high-quality videos can be recovered at roughly $60\times$ compression.

Compressive sensing enables the reconstruction of high-resolution signals from under-sampled data. While the compressive methods simplify data acquisition, they require the solution of difficult recovery problems to make use of the resulting measurements. This paper presents a new sensing framework that combines the advantages of both the conventional and the compressive sensing. Using the proposed sum-to-one transform, the measurements can be reconstructed instantly at the Nyquist rates at any power-of-two resolution. The same data can then be enhanced to higher resolutions using the compressive methods that leverage sparsity to beat the Nyquist limit. The availability of a fast direct reconstruction enables the compressive measurements to be processed on small embedded devices. We demonstrate this by constructing a real-time compressive video camera.

In this paper, we address the challenging problem of selecting tuning parameters for high-dimensional sparse regression. We propose a simple and computationally efficient method, called path thresholding PaTh, that transforms any tuning parameter-dependent sparse regression algorithm into an asymptotically tuning-free sparse regression algorithm. More specifically, we prove that, as the problem size becomes large (in the number of variables and in the number of observations), PaTh performs accurate sparse regression, under appropriate conditions, without specifying a tuning parameter. In finite-dimensional settings, we demonstrate that PaTh can alleviate the computational burden of model selection algorithms by significantly reducing the search space of tuning parameters.

This paper studies graphical model selection, i.e., the problem of estimating a graph of statistical relationships among a collection of random variables. Conventional graphical model selection algorithms are passive, i.e., they require all the measurements to have been collected before processing begins. We propose an active learning algorithm that uses junction tree representations to adapt future measurements based on the information gathered from prior measurements. We prove that, under certain conditions, our active learning algorithm requires fewer scalar measurements than any passive algorithm to reliably estimate a graph. A range of numerical results validate our theory and demonstrates the benefits of active learning.

We consider the efficient acquisition, parameter estimation, and recovery of signal ensembles that lie on a low-dimensional manifold in a high-dimensional ambient signal space. Our particular focus is on randomized, compressive acquisition of signals from the manifold generated by the transformation of a base signal by operators from a Lie group. Such manifolds factor prominently in a number of applications, including radar and sonar array processing, camera arrays, and video processing. Leveraging the fact that Lie group manifolds admit a convenient analytical characterization, we develop new theory and algorithms for: (1) estimating the Lie operator parameters from compressive measurements, and (2) recovering the base signal from compressive measurements. We validate our approach with several of numerical simulations, including the reconstruction of an affine-transformed video sequence from compressive measurements.

This paper deals with the recovery of an unknown, low-rank matrix from quantized and (possibly) corrupted measurements of a subset of its entries. We develop statistical models and corresponding (multi-)convex optimization algorithms for quantized matrix completion (Q-MC) and quantized robust principal component analysis (Q-RPCA). In order to take into account the quantized nature of the available data, we jointly learn the underlying quantization bin boundaries and recover the low-rank matrix, while removing potential (sparse) corruptions. Experimental results on synthetic and two real-world collaborative filtering datasets demonstrate that directly operating with the quantized measurements - rather than treating them as real values - results in (often significantly) lower recovery error if the number of quantization bins is less than about 10.

We propose SPARFA-Trace, a new machine learning-based framework for time-varying learning and content analytics for educational applications. We develop a novel message passing-based, blind, approximate Kalman filter for sparse factor analysis (SPARFA) that jointly traces learner concept knowledge over time, analyzes learner concept knowledge state transitions (induced by interacting with learning resources, such as textbook sections, lecture videos, etc., or the forgetting effect), and estimates the content organization and difficulty of the questions in assessments. These quantities are estimated solely from binary-valued (correct/incorrect) graded learner response data and the specific actions each learner performs (e.g., answering a question or studying a learning resource) at each time instant. Experimental results on two online course datasets demonstrate that SPARFA-Trace is capable of tracing each learner's concept knowledge evolution over time, analyzing the quality and content organization of learning resources, and estimating the question--concept associations and the question difficulties. Moreover, we show that SPARFA-Trace achieves comparable or better performance in predicting unobserved learner responses compared to existing collaborative filtering and knowledge tracing methods.

Alternating direction methods are a common tool for general mathematical programming and optimization. These methods have become particularly important in the field of variational image processing, which frequently requires the minimization of nondifferentiable objectives. This paper considers accelerated (i.e., fast) variants of two common alternating direction methods: the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). The proposed acceleration is of the form first proposed by Nesterov for gradient descent methods. In the case that the objective function is strongly convex, global convergence bounds are provided for both classical and accelerated variants of the methods. Numerical examples are presented to demonstrate the superior performance of the fast methods for a wide variety of problems.

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2κ randomized samples to recover a signal of complexity κ and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals.

Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.

Unions of subspaces have recently been shown to provide a compact nonlinear signal model for collections of high-dimensional data, such as large collections of images or videos. In this paper, we introduce a novel data-driven algorithm for learning unions of subspaces directly from a collection of data; our approach is based upon forming minimum ℓ2-norm (least-squares) representations of a signal with respect to other signals in the collection. The resulting representations are then used as feature vectors to cluster the data in accordance with each signal's subspace membership. We demonstrate that the proposed least-squares approach leads to improved classification performance when compared to state-of-the-art subspace clustering methods on both synthetic and real-world experiments. This study provides evidence that using least-squares methods to form data-driven representations of collections of data provide significant advantages over current methods that rely upon sparse representations.

Two open, online educational platforms, OpenStax Exercises and OpenStax Tutor, are working to revolutionize the way in which students learn concepts in diverse subject areas. Born and tested in the area of signal processing education, these tools bring to bear cutting-edge ideas in cognitive science and machine learning to automatically build personalized learning pathways for today's students and to advance the field of learning science. These platforms are introduced and initial results discussed.

We consider the problem of accurately estimating a high-dimensional sparse vector using a small number of linear measurements that are contaminated by noise. It is well known that standard computationally tractable sparse recovery algorithms, such as the Lasso, OMP, and their various extensions, perform poorly when the measurement matrix contains highly correlated columns. We develop a simple greedy algorithm, called SWAP, that iteratively swaps variables until a desired loss function cannot be decreased any further. SWAP is surprisingly effective in handling measurement matrices with high correlations. We prove that SWAP can be easily used as a wrapper around standard sparse recovery algorithms for improved performance. We theoretically quantify the statistical guarantees of SWAP and complement our analysis with numerical results on synthetic and real data.

Compressive sensing (CS) enables the acquisition and recovery of sparse signals and images at sampling rates significantly below the classical Nyquist rate. Despite significant progress in the theory and methods of CS, little headway has been made in compressive video acquisition and recovery. Video CS is complicated by the ephemeral nature of dynamic events, which makes direct extensions of standard CS imaging architectures and signal models difficult. In this paper, we develop a new framework for video CS for dynamic textured scenes that models the evolution of the scene as a linear dynamical system (LDS). This reduces the video recovery problem to first estimating the model parameters of the LDS from compressive measurements and then reconstructing the image frames. We exploit the low-dimensional dynamic parameters (the state sequence) and high-dimensional static parameters (the observation matrix) of the LDS to devise a novel compressive measurement strategy that measures only the time-varying parameters at each instant and accumulates measurements over time to estimate the time-invariant parameters. This enables us to lower the compressive measurement rate considerably. We validate our approach and demonstrate its effectiveness with a range of experiments involving video recovery and scene classification.

In compressive sensing, a small collection of linear projections of a sparse signal contains enough information to permit signal recovery. Distributed compressive sensing extends this framework by defining ensemble sparsity models, allowing a correlated ensemble of sparse signals to be jointly recovered from a collection of separately acquired compressive measurements. In this paper, we introduce a framework for modeling sparse signal ensembles that quantifies the intra- and intersignal dependences within and among the signals. This framework is based on a novel bipartite graph representation that links the sparse signal coefficients with the measurements obtained for each signal. Using our framework, we provide fundamental bounds on the number of noiseless measurements that each sensor must collect to ensure that the signals are jointly recoverable.

The compressive sensing (CS) framework aims to ease the burden on analog-to-digital converters (ADCs) by reducing the sampling rate required to acquire and stably recover sparse signals. Practical ADCs not only sample but also quantize each measurement to a finite number of bits; moreover, there is an inverse relationship between the achievable sampling rate and the bit depth. In this paper, we investigate an alternative CS approach that shifts the emphasis from the sampling rate to the number of bits per measurement. In particular, we explore the extreme case of 1-bit CS measurements, which capture just their sign. Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and provide a lower bound on the best achievable reconstruction error. We also demonstrate that i.i.d. random Gaussian matrices provide measurement mappings that, with overwhelming probability, achieve nearly optimal error decay. Next, we consider reconstruction robustness to measurement errors and noise and introduce the binary$\epsilon $-stable embedding property, which characterizes the robustness of the measurement process to sign changes. We show that the same class of matrices that provide almost optimal noiseless performance also enable such a robust mapping. On the practical side, we introduce the binary iterative hard thresholding algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.

Recovering a sparse signal from an undersampled set of random linear measurements is the main problem of interest in compressed sensing. In this paper, we consider the case where both the signal and the measurements are complex-valued. We study the popular recovery method ofl1-regularized least squares or LASSO. While several studies have shown that LASSO provides desirable solutions under certain conditions, the precise asymptotic performance of this algorithm in the complex setting is not yet known. In this paper, we extend the approximate message passing (AMP) algorithm to solve the complex-valued LASSO problem and obtain the complex approximate message passing algorithm (CAMP). We then generalize the state evolution framework recently introduced for the analysis of AMP to the complex setting. Using the state evolution, we derive accurate formulas for the phase transition and noise sensitivity of both LASSO and CAMP. Our theoretical results are concerned with the case of i.i.d. Gaussian sensing matrices. Simulations confirm that our results hold for a larger class of random matrices.

We develop a new method for tracking narrowband signals acquired via compressive sensing. The compressive sensing phase-locked loop (CS-PLL) enables one to track oscillating signals in very large bandwidths using sub-Nyquist sampling. A key feature of the approach is the fact that we perform the frequency tracking directly on the compressive measurements without ever recovering the signal. The CS-PLL has a wide variety of potential applications, including communications, phase tracking, and robust control.

In this paper, we investigate dictionary learning (DL) from sparsely corrupted or compressed signals. We consider three cases: I) the training signals are corrupted, and the locations of the corruptions are known, II) the locations of the sparse corruptions are unknown, and III) DL from compressed measurements, as it occurs in blind compressive sensing. We develop two efficient DL algorithms that are capable of learning dictionaries from sparsely corrupted or compressed measurements. Empirical phase transitions and an in-painting example demonstrate the capabilities of our algorithms.

We introduce a novel analog-to-digital converter (ADC) based on the traditional successive approximation register. This architecture employs compressive sensing (CS) techniques to acquire and reconstruct frequency sparse signals. One important difference between our approach and traditional CS systems is that our architecture constrains the number of bits used during acquisition rather than the number of measurements. Our system is able to flexibly partition a fixed budget in order to trade the number of measurements it acquires with the quantization depth given to each measurement. We show that this degree of flexibility is particularly advantageous for ameliorating the CS noise folding phenomenon, allowing our ADC significant gains over measurement-constrained compressive sensing systems.

Compressive sensing (CS)-based spatial-multiplexing cameras (SMCs) sample a scene through a series of coded projections using a spatial light modulator and a few optical sensor elements. SMC architectures are particularly useful when imaging at wavelengths for which full-frame sensors are too cumbersome or expensive. While existing recovery algorithms for SMCs perform well for static images, they typically fail for time-varying scenes (videos). In this paper, we propose a novel CS multi-scale video (CS-MUVI) sensing and recovery framework for SMCs. Our framework features a co-designed video CS sensing matrix and recovery algorithm that provide an efficiently computable low-resolution video preview. We estimate the scene's optical flow from the video preview and feed it into a convex-optimization algorithm to recover the high-resolution video. We demonstrate the performance and capabilities of the CS-MUVI framework for different scenes.

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high-dimensional ambient space. We introduce Successive Projection onto INcoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current signal recovery models and algorithms for low-dimensional linear inverse problems, and matches (or exceeds) the current state of the art in terms of performance.

A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist “universal” algorithms for recovering “structured” signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements.

Compressive sensing (CS) is an emerging approach for the acquisition of signals having a sparse or compressible representation in some basis. While the CS literature has mostly focused on problems involving 1-D signals and 2-D images, many important applications involve multidimensional signals; the construction of sparsifying bases and measurement systems for such signals is complicated by their higher dimensionality. In this paper, we propose the use of Kronecker product matrices in CS for two purposes. First, such matrices can act as sparsifying bases that jointly model the structure present in all of the signal dimensions. Second, such matrices can represent the measurement protocols used in distributed settings. Our formulation enables the derivation of analytical bounds for the sparse approximation of multidimensional signals and CS recovery performance, as well as a means of evaluating novel distributed measurement schemes.

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear submanifold of a high-dimensional ambient space. We introduce successive projections onto incoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low-dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance.

The recently developed compressive sensing (CS) framework enables the design of sub-Nyquist analog-to-digital converters. Several architectures have been proposed for the acquisition of sparse signals in large swaths of bandwidth. In this paper we consider a more flexible multi-channel signal model consisting of several discontiguous channels where the occupancy of the combined bandwidth of the channels is sparse. We introduce a new compressive acquisition architecture, the compressive multiplexer (CMUX), to sample such signals. We demonstrate that our architecture is CS-feasible and suggest a simple implementation with numerous practical advantages.

Compressed sensing (CS) exploits the compressibility of natural signals to reduce the number of samples required for accurate reconstruction. The cost for sub-Nyquist sampling has been computationally expensive reconstruction algorithms, including large-scale ℓ1optimization. Therefore, first-order optimization methods that exploit only the gradient of the reconstruction cost function have been developed; notable examples include iterative soft thresholding (IST), fast iterative soft thresholding algorithm (FISTA), and approximate message passing (AMP). The performance of these algorithms has been studied mainly in the standard framework of convex optimization, called the deterministic framework here. In this paper, we first show that the deterministic approach results in overly pessimistic conclusions that are not indicative of algorithm performance in practice. As an alternative to the deterministic framework, we second study the theoretical aspects of the statistical convergence rate, a topic that has remained unexplored in the sparse recovery literature. Our theoretical and empirical studies reveal several hallmark properties of the statistical convergence of first-order methods, including universality over the matrix ensemble and the least favorable coefficient distribution.

We consider the problem of recovering a matrix $\mathbf{M}$ that is the sum of a low-rank matrix $\mathbf{L}$ and a sparse matrix $\mathbf{S}$ from a small set of linear measurements of the form $\mathbf{y} = \mathcal{A}(\mathbf{M}) = \mathcal{A}({\bf L}+{\bf S})$. This model subsumes three important classes of signal recovery problems: compressive sensing, affine rank minimization, and robust principal component analysis. We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it. SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation. Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm.

Compressive sensing (CS) is an emerging approach for acquisition of signals having a sparse or compressible representation in some basis. While CS literature has mostly focused on problems involving 1-D and 2-D signals, many important applications involve signals that are multidimensional. We propose the use of Kronecker product matrices in CS for two purposes. First, we can use such matrices as sparsifying bases that jointly model the different types of structure present in the signal. Second, the measurement matrices used in distributed measurement settings can be easily expressed as Kronecker products. This new formulation enables the derivation of analytical bounds for sparse approximation and CS recovery of multidimensional signals.

Compressive Sensing (CS) has emerged as a potentially viable technique for the efficient acquisition of high-resolution signals and images that have a sparse representation in a fixed basis. The number of linear measurements M required for robust polynomial time recovery of S-sparse signals of length N can be shown to be proportional to S log N. However, in many real-life imaging applications, the original S-sparse image may be blurred by an unknown point spread function defined over a domain O; this multiplies the apparent sparsity of the image, as well as the corresponding acquisition cost, by a factor of |Ω|. In this paper, we propose a new CS recovery algorithm for such images that can be modeled as a sparse superposition of pulses. Our method can be used to infer both the shape of the two-dimensional pulse and the locations and amplitudes of the pulses. Our main theoretical result shows that our reconstruction method requires merely M = O(S + |Ω|) linear measurements, so that M is sublinear in the overall image sparsity S|Ω|. Experiments with real world data demonstrate that our method provides considerable gains over standard state-of-the-art compressive sensing techniques in terms of numbers of measurements required for stable recovery.

This paper develops a new class of algorithms for signal recovery in the distributed compressive sensing (DCS) framework. DCS exploits both intra-signal and inter-signal correlations through the concept of joint sparsity to further reduce the number of measurements required for recovery. DCS is well-suited for sensor network applications due to its universality, computational asymmetry, tolerance to quantization and noise, and robustness to measurement loss. In this paper we propose recovery algorithms for the sparse common and innovation joint sparsity model. Our approach leads to a class of efficient algorithms, the Texas Hold 'Em algorithms, which are scalable both in terms of communication bandwidth and computational complexity.

This paper studies the training of support vector machine (SVM) classifiers with respect to the minimax and Neyman-Pearson criteria. In principle, these criteria can be optimized in a straightforward way using a cost-sensitive SVM. In practice, however, because these criteria require especially accurate error estimation, standard techniques for tuning SVM parameters, such as cross-validation, can lead to poor classifier performance. To address this issue, we first prove that the usual cost-sensitive SVM, here called the 2C-SVM, is equivalent to another formulation called the 2nu-SVM. We then exploit a characterization of the 2nu-SVM parameter space to develop a simple yet powerful approach to error estimation based on smoothing. In an extensive experimental study, we demonstrate that smoothing significantly improves the accuracy of cross-validation error estimates, leading to dramatic performance gains. Furthermore, we propose coordinate descent strategies that offer significant gains in computational efficiency, with little to no loss in performance.

Sparse representation and compressive sensing establishes a more rigorous mathematical framework for studying high-dimensional data and ways to uncover the structures of the data, giving rise to a large repertoire of efficient algorithms. A sparse signal is a signal that can be represented as a linear combination of relatively few base elements in a basis or an overcomplete dictionary. A sufficiently sparse linear representation can be correctly and efficiently computed by greedy methods and convex optimization (i.e., the l1-l0equivalence), even though this problem is extremely difficult-NP-hard in the general case.

We compare and contrast from a geometric perspective a number of low-dimensional signal models that support stable information-preserving dimensionality reduction. We consider sparse and compressible signal models for deterministic and random signals, structured sparse and compressible signal models, point clouds, and manifold signal models. Each model has a particular geometrical structure that enables signal information to be stably preserved via a simple linear and nonadaptive projection to a much lower dimensional space; in each case the projection dimension is independent of the signal's ambient dimension at best or grows logarithmically with it at worst. As a bonus, we point out a common misconception related to probabilistic compressible signal models, namely, by showing that the oft-used generalized Gaussian and Laplacian models do not support stable linear dimensionality reduction.

The emergence of low-cost sensing architectures for diverse modalities has made it possible to deploy sensor networks that capture a single event from a large number of vantage points and using multiple modalities. In many scenarios, these networks acquire large amounts of very high-dimensional data. For example, even a relatively small network of cameras can generate massive amounts of high-dimensional image and video data. One way to cope with this data deluge is to exploit low-dimensional data models. Manifold models provide a particularly powerful theoretical and algorithmic framework for capturing the structure of data governed by a small number of parameters, as is often the case in a sensor network. However, these models do not typically take into account dependencies among multiple sensors. We thus propose a new joint manifold framework for data ensembles that exploits such dependencies. We show that joint manifold structure can lead to improved performance for a variety of signal processing algorithms for applications including classification and manifold learning. Additionally, recent results concerning random projections of manifolds enable us to formulate a scalable and universal dimensionality reduction scheme that efficiently fuses the data from all sensors.

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K ¿ N elements from an N -dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from M = O(K log(N/K)) measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal models-wavelet trees and block sparsity-into two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M = O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.

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

We study the representation, approximation, and compression of functions inMdimensions that consist of constant or smooth regions separated by smooth(M-1)-dimensional discontinuities. Examples include images containing edges, video sequences of moving objects, and seismic data containing geological horizons. For both function classes, we derive the optimal asymptotic approximation and compression rates based on Kolmogorov metric entropy. For piecewise constant functions, we develop a multiresolution predictive coder that achieves the optimal rate-distortion performance; for piecewise smooth functions, our coder has near-optimal rate-distortion performance. Our coder for piecewise constant functions employssurflets, a new multiscale geometric tiling consisting ofM-dimensional piecewise constant atoms containing polynomial discontinuities. Our coder for piecewise smooth functions usessurfprints, which wed surflets to wavelets for piecewise smooth approximation. Both of these schemes achieve the optimal asymptotic approximation performance. Key features of our algorithms are that they carefully control the potential growth in surflet parameters at higher smoothness and do not require explicit estimation of the discontinuity. We also extend our results to the corresponding discrete function spaces for sampled data. We provide asymptotic performance results for both discrete function spaces and relate this asymptotic performance to the sampling rate and smoothness orders of the underlying functions and discontinuities. For approximation of discrete data, we propose a new scale-adaptive dictionary that contains few elements at coarse and fine scales, but many elements at medium scales. Simulation results on synthetic signals provide a comparison between surflet-based coders and previously studied approximation schemes based on wedgelets and wavelets.

Compressive sensing microarrays (CSM) are DNA-based sensors that operate using the principle of compressive sensing (CS). In contrast to conventional DNA microarrays, in which each genetic sensor is designed to respond to a single target, in a CSM each sensor responds to a group of targets. We study the problem of designing CS probes that simultaneously account for both the constraints from group testing theory and the biochemistry of probe-target DNA hybridization. Our results show that, in order to achieve accurate hybridization profiling, consensus probe sequences are required to have sequence homology of at least 80% with all targets to be detected. Furthermore, experiments show that out-of-equilibrium datasets are usually as accurate as those obtained from equilibrium conditions. Consequently, one can use CSMs in applications for which only short hybridization times are allowed.

Classical sampling records the signal level at pre-determined time instances, usually uniformly spaced. An alternative implicit sampling model is to record the timing of pre-determined level crossings. Thus the signal dictates the sampling times but not the sampling levels. Logan's theorem provides sufficient conditions for a signal to be recoverable, within a scaling factor, from only the timing of its zero crossings. Unfortunately, recovery from noisy observations of the timings is not robust and usually fails to reproduce the original signal. To make the reconstruction robust this paper introduces the additional assumption that the signal is sparse in some basis. We reformulate the reconstruction problem as a minimization of a sparsity inducing cost function on the unit sphere and provide an algorithm to compute the solution. While the problem is not convex, simulation studies indicate that the algorithm converges in typical cases and produces the correct solution with very high probability.

Compressive sensing aims to recover a sparse or compressible signal from a small set of projections onto random vectors; conventional solutions involve linear programming or greedy algorithms that can be computationally expensive. Moreover, these recovery techniques are generic and assume no particular structure in the signal aside from sparsity. In this paper, we propose a new algorithm that enables fast recovery of piecewise smooth signals, a large and useful class of signals whose sparse wavelet expansions feature a distinct "connected tree" structure. Our algorithm fuses recent results on iterative reweighted pound1-norm minimization with the wavelet Hidden Markov Tree model. The resulting optimization-based solver outperforms the standard compressive recovery algorithms as well as previously proposed wavelet-based recovery algorithms. As a bonus, the algorithm reduces the number of measurements necessary to achieve low-distortion reconstruction.

In this paper, we successfully demonstrate the feasibility of hardware implementation of a sub-Nyquist random sampling based analog to information converter (RS-AIC). The RS-AIC is based on the theory of information recovery from random samples using an efficient information recovery algorithm to compute the spectrogram of the signal. Our RS-AIC enables sub-Nyquist acquisition and processing of wideband signals that are sparse in a local Fourier representation. Results from our RS-AIC hardware implementation demonstrate successful reconstruction of signals that are sampled at half the Nyquist-rate while maintaining up to a 51 dB signal-to-noise ratio (SNR), which is equivalent to an 8.5 bit resolution analog to digital converter.

Compressive Sensing (CS) combines sampling and compression into a single sub-Nyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefficients are clustered. Our new model-based reconstruction algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms.

While evidence indicates that neural systems may be employing sparse approximations to represent sensed stimuli, the mechanisms underlying this ability are not understood. We describe a locally competitive algorithm (LCA) that solves a collection of sparse coding principles minimizing a weighted combination of mean-squared error and a coefficient cost function. LCAs are designed to be implemented in a dynamical system composed of many neuron-like elements operating in parallel. These algorithms use thresholding functions to induce local (usually one-way) inhibitory competitions between nodes to produce sparse representations. LCAs produce coefficients with sparsity levels comparable to the most popular centralized sparse coding algorithms while being readily suited for neural implementation. Additionally, LCA coefficients for video sequences demonstrate inertial properties that are both qualitatively and quantitatively more regular (i.e., smoother and more predictable) than the coefficients produced by greedy algorithms.

Over the last 15 years, the Internet has enabled new modes of authorship, new forms of open licensing and distribution, and new forms of collaboration and peer production to flourish. But in turn, new anxieties have arisen, especially concerning quality assurance, peer review, reuse, and modification. New innovations are appearing in peer review, endorsement, the measurement of trust, and the understanding of reputation, but without any systematic analysis of the general principles of quality assurance and peer review in this new era. In this paper, we propose a general set of principles for understanding what peer review was in the past and how it should be applied today to different kinds of content and in new platforms for managing quality. The principles stress an analysis not only on the content in materials but also on their context of use. Our focus is on open educational resources, and we present a case study of the open education project Connexions' lens system for quality assurance and review. However, the principles can be applied across multiple levels of knowledge production, including scholarship in engineering and science and reference materials in addition to educational publishing.

The dual-tree quaternion wavelet transform (QWT) is a new multiscale analysis tool for geometric image features. The QWT is a near shift-invariant tight frame representation whose coefficients sport a magnitude and three phases: two phases encode local image shifts while the third contains image texture information. The QWT is based on an alternative theory for the 2-D Hilbert transform and can be computed using a dual-tree filter bank with linear computational complexity. To demonstrate the properties of the QWT's coherent magnitude/phase representation, we develop an efficient and accurate procedure for estimating the local geometrical structure of an image. We also develop a new multiscale algorithm for estimating the disparity between a pair of images that is promising for image registration and flow estimation applications. The algorithm features multiscale phase unwrapping, linear complexity, and sub-pixel estimation accuracy.

Compressive sensing (CS) is a new signal acquisition technique for sparse and compressible signals. Rather than uniformly sampling the signal, CS computes inner products with randomized basis functions; the signal is then recovered by a convex optimization. Random CS measurements are universal in the sense that the same acquisition system is sufficient for signals sparse in any representation. This paper examines the quantization of strictly sparse, power-limited signals and concludes that CS with scalar quantization uses its allocated rate inefficiently. The results complement related work on the quantization of CS measurements of compressible signals.

We propose a framework for exploiting dimension-reducing random projections in detection and classification problems. Our approach is based on the generalized likelihood ratio test; in the case of image classification, it exploits the fact that a set of images of a fixed scene under varying articulation parameters forms a low-dimensional, nonlinear manifold. Exploiting recent results showing that random projections stably embed a smooth manifold in a lower-dimensional space, we develop the multiscale smashed filter as a compressive analog of the familiar matched filter classifier. In a practical target classification problem using a single-pixel camera that directly acquires compressive image projections, we achieve high classification rates using many fewer measurements than the dimensionality of the images.

Practical sparse approximation algorithms (particularly greedy algorithms) suffer two significant drawbacks: they are difficult to implement in hardware, and they are inefficient for time-varying stimuli (e.g., video) because they produce erratic temporal coefficient sequences. We present a class of locally competitive algorithms (LCAs) that correspond to a collection of sparse approximation principles minimizing a weighted combination of reconstruction MSE and a coefficient cost function. These systems use thresholding functions to induce local nonlinear competitions in a dynamical system. Simple analog hardware can implement the required nonlinearities and competitions. We show that our LCAs are stable under normal operating conditions and can produce sparsity levels comparable to existing methods. Additionally, these LCAs can produce coefficients for video sequences that are more regular (i.e., smoother and more predictable) than the coefficients produced by greedy algorithms.

In this paper we propose a new blind, error-free detection algorithm for watermarking in transform domains. The detection scheme uses linear decoding techniques from the theory of compressive sensing (CS), whose central idea is that a small number of non-adaptive linear projections of a sparse signal are sufficient for error-free reconstruction of the original signal. We use the fact that natural images are approximately sparse in the DCT or wavelet basis; with an extra step of sparsification or scaling of the coefficients we can decode both the original image and watermark with zero error, despite not knowing the host image. Besides being error-free, our proposed detection algorithm has low complexity compared to other blind algorithms. It can be extended to any transform-domain watermarking method, and also be used to watermark already compressed images.

The new theory of compressive sensing enables direct analog-to-information conversion of compressible signals at sub-Nyquist acquisition rates. The authors develop new theory, algorithms, performance bounds, and a prototype implementation for an analog-to-information converter based on random demodulation. The architecture is particularly apropos for wideband signals that are sparse in the time-frequency plane. End-to-end simulations of a complete transistor-level implementation prove the concept under the effect of circuit nonidealities.

We propose a novel method for {\em linear} dimensionality reduction of manifold modeled data. First, we show that with a small number $M$ of {\em random projections} of sample points in $\reals^N$ belonging to an unknown $K$-dimensional Euclidean manifold, the intrinsic dimension (ID) of the sample set can be estimated to high accuracy. Second, we rigorously prove that using only this set of random projections, we can estimate the structure of the underlying manifold. In both cases, the number random projections required is linear in $K$ and logarithmic in $N$, meaning that $K

We study lattice bases where the angle between any basis vector and the linear subspace spanned by the other basis vectors is at least $\frac{\pi}{3}$ radians; we denote such bases as “nearly orthogonal.” We show that a nearly orthogonal lattice basis always contains a shortest lattice vector. Moreover, we prove that if the basis vector lengths are “nearly equal,” then the basis is the unique nearly orthogonal lattice basis up to multiplication of basis vectors by $\pm 1$. We also study random lattices generated by the columns of random matrices with n rows and $m \leq n$ columns. We show that if $m \leq c\,n$, with $c \approx 0.071$, then the random matrix forms a nearly orthogonal basis for the random lattice with high probability for large n and almost surely as n tends to infinity. Consequently, the columns of such a random matrix contain the shortest vector in the random lattice. Finally, we discuss an interesting JPEG image compression application where nearly orthogonal lattice bases play an important role.

Multi-input single-output deconvolution (MISO-D) aims to extract a deblurred estimate of a target signal from several blurred and noisy observations. This paper develops a new two step framework--Texas Two-Step--to solve MISO-D problems with known blurs. Texas Two-Step first reduces the MISO-D problem to a related single-input single-output deconvolution (SISO-D) problem by invoking the concept of sufficient statistics (SSs) and then solves the simpler SISO-D problem using an appropriate technique. The two-step framework enables new MISO-D techniques (both optimal and suboptimal) based on the rich suite of existing SISO-D techniques. In fact, the properties of SSs imply that a MISO-D algorithm is mean-squared-error optimal if and only if it can be rearranged to conform to the Texas Two-Step framework. Using this insight, we construct new wavelet- and curvelet-based MISO-D algorithms with asymptotically optimal performance. Simulated and real data experiments verify that the framework is indeed effective.

We study the problem of designing support vector classifiers with respect to a Neyman-Pearson criterion. Specifically, given a user-specified level alpha isin (0,1), how can we ensure a false alarm rate no greater than q while minimizing the miss rate? We examine two approaches, one based on shifting the offset of a conventionally trained SVM and the other based on the introduction of class-specific weights. Our contributions include a novel heuristic for improved error estimation and a strategy for efficiently searching the parameter space of the second method. We also provide a characterization of the feasible parameter set of the 2v-SVM on which the second approach is based. The proposed methods are compared on four benchmark datasets

The recently introduced theory of compressed sensing (CS) enables the reconstruction or approximation of sparse or compressible signals from a small set of incoherent projections; often the number of projections can be much smaller than the number of Nyquist rate samples. In this paper, we show that the CS framework is information scalable to a wide range of statistical inference tasks. In particular, we demonstrate how CS principles can solve signal detection problems given incoherent measurements without ever reconstructing the signals involved. We specifically study the case of signal detection in strong inference and noise and propose an incoherent detection and estimation algorithm (IDEA) based on matching pursuit. The number of measurements and computations necessary for successful detection using IDEA is significantly lower than that necessary for successful reconstruction. Simulations show that IDEA is very resilient to strong interference, additive noise, and measurement quantization. When combined with random measurements, IDEA is applicable to a wide range of different signal classes

We propose and study a new technique for efficiently acquiring and reconstructing signals based on convolution with a fixed FIR filter having random taps. The method is designed for sparse and compressible signals, i.e., ones that are well approximated by a short linear combination of vectors from an orthonormal basis. Signal reconstruction involves a nonlinear orthogonal matching pursuit algorithm that we implement efficiently by exploiting the nonadaptive, time-invariant structure of the measurement process. While simpler and more efficient than other random acquisition techniques like compressed sensing, random filtering is sufficiently generic to summarize many types of compressible signals and generalizes to streaming and continuous-time signals. Extensive numerical experiments demonstrate its efficacy for acquiring and reconstructing signals sparse in the time, frequency, and wavelet domains, as well as piecewise smooth signals and Poisson processes

Random projections have recently found a surprising niche in signal processing. The key revelation is that the relevant structure in a signal can be preserved when that signal is projected onto a small number of random basis functions. Recent work has exploited this fact under the rubric of compressed sensing (CS): signals that are sparse in some basis can be recovered from small numbers of random linear projections. In many cases, however, we may have a more specific low-dimensional model for signals in which the signal class forms a nonlinear manifold in RN. This paper provides preliminary theoretical and experimental evidence that manifold-based signal structure can be preserved using small numbers of random projections. The key theoretical motivation comes from Whitney's embedding theorem, which states that a K-dimensional manifold can be embedded in Ropf2K+1. We examine the potential applications of this fact. In particular, we consider the task of recovering a manifold-modeled signal from a small number of random projections. Thanks to our more specific model, we can recover certain signals using far fewer measurements than would be required using sparsity-driven CS techniques

We propose an efficient multiscale image disparity estimation algorithm that estimates the local translations needed to align different regions in two images. The algorithm is based on the dual-tree quaternion wavelet transform (QWT). Each QWT coefficient features a magnitude and three phase angles; we exploit the fact that two of the phase angles are covariant with image shifts in the horizontal and vertical directions. By fusing phase information across multiple scales, we combat the phase unwrapping problem that has traditionally plagued phase-based disparity estimation techniques. The result is a linear-time algorithm that provides reliable estimates of both small and large image shifts. The algorithm is completely image-based; that is, it involves no extraction of feature points or other landmarks. It can be used as a front-end for image processing and computer vision tasks such as image registration, motion estimation, and stereo matching. We present results with a real-world image sequence.

Compressive sensing is an emerging field based on the rev elation that a small group of non-adaptive linear projections of a compressible signal contains enough information for reconstruction and processing. In this paper, we propose algorithms and hardware to support a new theory of compressive imaging. Our approach is based on a new digital image/video camera that directly acquires random projections of the signal without first collecting the pixels/voxels. Our camera architecture employs a digital micromirror array to perform optical calculations of linear projections of an image onto pseudorandom binary patterns. Its hallmarks include the ability to obtain an image with a single detection element while measuring the image/video fewer times than the number of pixels this can significantly reduce the computation required for video acquisition/encoding. Because our system relies on a single photon detector, it can also be adapted to image at wavelengths that are currently impossible with conventional CCD and CMOS imagers. We are currently testing a proto type design for the camera and include experimental results.

This paper develops a new framework for distributed coding and compression in sensor networks based on distributed compressed sensing (DCS). DCS exploits both intra-signal and inter-signal correlations through the concept of joint sparsity; just a few measurements of a jointly sparse signal ensemble contain enough information for reconstruction. DCS is well-suited for sensor network applications, thanks to its simplicity, universality, computational asymmetry, tolerance to quantization and noise, robustness to measurement loss, and scalability. It also requires absolutely no inter-sensor collaboration. We apply our framework to several real world datasets to validate the framework.

Distributed wavelet processing within sensor networks holds promise for reducing communication energy and wireless bandwidth usage at sensor nodes. Local collaboration among nodes de-correlates measurements, yielding a sparser data set with significant values at far fewer nodes. Sparsity can then be leveraged for subsequent processing such as measurement compression, de-noising, and query routing. A number of factors complicate realizing such a transform in real-world deployments, including irregular spatial placement of nodes and a potentially prohibitive energy cost associated with calculating the transform in-network. In this paper, we address these concerns head-on; our contributions are fourfold. First, we propose a simple interpolatory wavelet transform for irregular sampling grids. Second, using ns-2 simulations of network traffic generated by the transform, we establish for a variety of network configurations break-even points in network size beyond which multiscale data processing provides energy savings. Distributed lossy compression of network measurements provides a representative application for this study. Third, we develop a new protocol for extracting approximations given only a vague notion of source statistics and analyze its energy savings over a more intuitive but naïve approach. Finally, we extend the 2-dimensional (2-D) spatial irregular grid transform to a 3-D spatio-temporal transform, demonstrating the substantial gain of distributed 3-D compression over repeated 2-D compression.

Sudocodes are a new scheme for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse signal x isin RopfNcontaining only K Lt N non-zero values. Sudo-encoding computes the codeword via the linear matrix-vector multiplication y = Phix, with K < M Lt N. We propose a non-adaptive construction of a sparse Phi comprising only the values 0 and 1; hence the computation of y involves only sums of subsets of the elements of x. An accompanying sudodecoding strategy efficiently recovers x given y. Sudocodes require only M = O(Klog(N)) measurements for exact reconstruction with worst-case computational complexity O(Klog(K) log(N)). Sudocodes can be used as erasure codes for real-valued data and have potential applications in peer-to-peer networks and distributed data storage systems. They are also easily extended to signals that are sparse in arbitrary bases

We routinely encounter digital color images that were previously compressed using the Joint Photographic Experts Group (JPEG) standard. En route 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, this paper aims to estimate its lost JPEG CH. We observe that the previous JPEG compression's quantization step introduces a lattice structure in the discrete cosine transform (DCT) domain. This paper proposes two approaches that exploit this structure to solve the JPEG Compression History Estimation (CHEst) problem. First, we design a statistical dictionary-based CHEst algorithm that tests the various CHs in a dictionary and selects the maximum a posteriori estimate. Second, for cases where the DCT coefficients closely conform to a 3-D parallelepiped lattice, we design a blind lattice-based CHEst algorithm. The blind algorithm exploits the fact that the JPEG CH is encoded in the nearly orthogonal bases for the 3-D lattice and employs novel lattice algorithms and recent results on nearly orthogonal lattice bases to estimate the CH. Both algorithms provide robust JPEG CHEst performance in practice. Simulations demonstrate that JPEG CHEst can be 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.

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

Rissanen provided a sequential universal coding algorithm based on a block partitioning scheme, where the source model is estimated at the beginning of each block. This approach asymptotically approaches the entropy at the fastest possible rate of 1/2log(n) bits per unknown parameter. We show that the complexity of this algorithm is /spl Omega/(nlog(n)), which is comparable to existing sequential universal algorithms. We provide a sequential O(nlog(log(n))) algorithm by modifying Rissanen's block partitioning scheme. The redundancy with our approach is greater than with Rissanen's block partitioning scheme by a multiplicative factor 1+O(1/log(log(n))), hence it asymptotically approaches the entropy at the fastest possible rate.

Many real world data sets can be viewed as points in a higher-dimensional space that lie concentrated around a lower-dimensional manifold structure. We propose a new multiscale representation for such point clouds based on lifting and perfect matching. The result is an adaptive wavelet transform that decomposes a point cloud into manifold approximations and details at multiple scales. We illustrate with several examples that the transform can extract an unknown smooth manifold from noisy point cloud samples using simple wavelet thresholding ideas.

Though several wavelet-based compression solutions for wireless sensor network measurements have been proposed, no such technique has yet appreciated the need to couple a wavelet transform tolerant of irregularly sampled data with the data transport protocol governing communications in the network. As power is at a premium in sensor nodes, such a technique is necessary to reduce costly communication overhead. To this end, we present an irregular wavelet transform capable of adapting to an arbitrary, multiscale network routing hierarchy. Inspired by the Haar wavelet in the regular setting, our wavelet basis forms a tight frame adapted to the structure of the network. We demonstrate results highlighting the approximation capabilities of such a transform and the clear reduction in communication cost when transmitting a compressed snapshot of the network to an outside user.

The images generated by varying the underlying articulation parameters of an object (pose, attitude, light source position, and so on) can be viewed as points on a low-dimensional image parameter articulation manifold (IPAM) in a high-dimensional ambient space. In this paper, we develop 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 develop a new algorithm for high-accuracy parameter estimation based on a coarse-to-fine Newton iteration through the family of approximate tangent spaces. We test the algorithm in several idealized registration and pose estimation problems.

High capacity data transfers over the Internet routinely fail to meet end-to-end performance expectations. The default transport control protocol for best effort data traffic is currently TCP, which does not scale well to 100 Mbps and higher networks over long distances. In congestion avoidance, TCP is not swift enough to fully utilize resources over paths with a high delay bandwidth product. First attempts to alleviate this problem by equipping TCP with increased aggressiveness have shown the disadvantage of poor fairness with the ubiquitous standard TCP-Reno, or in some cases, even among two connections running over the same path. We propose a new delay sensitive-congestion avoidance mode (TCP-Africa) that allows for scalable, aggressive behavior in large underutilized links, yet falls back to the more conservative TCP-Reno algorithm once links become well utilized and congestion is imminent. Through ns2 simulations we argue for the safety, efficiency, and fairness of TCP-Africa.

Compressed sensing is an emerging field based on the revelation that a small group of linear projections of a sparse signal contains enough information for reconstruc- tion. In this paper we introduce a new theory for distributed compressed sensing (DCS) that enables new distributed coding algorithms for multi-signal ensembles that exploit both intra- and inter-signal correlation structures. The DCS theory rests on a new concept that we term the joint sparsity of a signal ensemble. We study three simple models for jointly sparse signals, propose algorithms for joint recov- ery of multiple signals from incoherent projections, and characterize theoretically and empirically the number of measurements per sensor required for accurate re- construction. In some sense DCS is a framework for distributed compression of sources with memory, which has remained a challenging problem in information theory for some time. DCS is immediately applicable to a range of problems in sensor networks and arrays.

The fading channels seen in many wireless systems provide a particularly hostile environment for reliable communication. Current metrics for evaluating the performance limits of fading channels have shortcomings. Ergodic capacity, representing the ultimate error-free communications limit, only applies to systems with infinite coding delay. Practical systems are delay-limited and must use finite-length codes. For delay-limited systems /spl epsi/-capacity and delay-limited capacity are typically used to quantify the communications performance. However, /spl epsi/-capacity is not an estimate of error-free performance while delay-limited capacity tends to be an overly conservative measure. We model practical systems as a single server queue and quantify the communications performance as the average throughput through the queue. Throughput is maximized by optimally selecting the transmission rate and power control strategy. Using this approach we arrive at striking conclusions. First, we show that a throughput very close to ergodic capacity can be achieved with a small coding delay. Second, the optimal transmission rate for some systems can be higher than the ergodic capacity of the channel. Third, we demonstrate the notion that power adaptation does not improve communication performance does not hold for delay-limited systems.

We extend the wavelet transform to handle multidimensional signals that are smooth save for singularities along lower-dimensional manifolds. We first generalize the complex wavelet transform to higher dimensions using a multidimensional 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 1D dual-tree complex wavelet transform along each signal axis. We demonstrate how the HWT can be used for fast line detection in 3D.

The directionality and phase information provided by nonredundant complex wavelet transforms (NCWTs) provide significant potential benefits for image/video processing and compression applications. However, because existing NCWTs are created by downsampling filtered wavelet coefficients, the finest scale of these transforms has a resolution 4/spl times/ lower than the real input signal. In this paper, we propose a linear-phase, semi-orthogonal, directional NCWT design using a novel triband filter bank. At the finest scale, the resulting transform has a resolution 3/spl times/ lower than the real input signal. We provide a design example to demonstrate three important properties for image/video processing applications: directionality, magnitude coherency, and phase coherency.

We introduce a generalized definition for "low-pass" filters that covers time-varying and nonlinear systems under the same umbrella. We show that the qualitative concept of signal smoothing can be made precise through the concept of contractions in probabilistic metric spaces. For illustration, we consider classical linear time-invariant low-pass filters, nonlinear median filters, and time-varying guaranteed maximum delay schedulers employed in communication systems.

Using the concepts of two-dimensional Hubert transform and analytic signal, we construct a new quaternion wavelet transform (QWT). The QWT forms a tight frame and can be efficiently computed using a-2-D dual-tree filter bank. The QWT and the 2-D complex wavelet transform (CWT) are related by a unitary transformation, but the former inherits the quaternion Fourier-transform (QFT) phase properties, which are desirable for image analysis. The quaternion magnitude-phase representation of the QWT directly leads to near shift-invariance and the ability to encode phase shifts in an absolute x-y-coordinate system, which we can use for applications such as edge estimation and statistical image modeling.

We propose a new iterative distributed algorithm for linear minimum mean-squared-error (LMMSE) estimation in sensor networks whose measurements follow a Gaussian hidden Markov graphical model with cycles. The embedded polygons algorithm decomposes a loopy graphical model into a number of linked embedded polygons and then applies a parallel block Gauss-Seidel iteration comprising local LMMSE estimation on each polygon (involving inversion of a small matrix) followed by an information exchange between neighboring nodes and polygons. The algorithm is robust to temporary communication faults such as link failures and sleeping nodes and enjoys guaranteed convergence under mild conditions. A simulation study indicates 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.

Discontinuities in data often provide vital information, and representing these discontinuities sparsely is an important goal for approximation and compression algorithms. Little work has been done on efficient representations for higher dimensional functions containing arbitrarily smooth discontinuities. We consider the N-dimensional Horizon class-N-dimensional functions containing a C/sup K/ smooth (N-1)-dimensional singularity separating two constant regions. We derive the optimal rate-distortion function for this class and introduce the multiscale surflet representation for sparse piecewise approximation of these functions. We propose a compression algorithm using surflets that achieves the optimal asymptotic rate-distortion performance for Horizon functions. This algorithm can be implemented using knowledge of only the N-dimensional function, without explicitly estimating the (N-1)-dimensional discontinuity.

We study the problem of locating in space and over time a network pathâ s tight link, that is the link with the least available bandwidth on the path. Tight link localization benefits network-aware applications, provides insight into the causes of network congestion and ways to circumvent it, and aids network operations. We present STAB, a light-weight probing tool to locate tight links. STAB combines the probing concepts of self-induced congestion, tailgating, and packet chirps in a novel fashion. We demonstrate its capabilities through experiments on the Internet and verify our results using router MRTG data.

We propose a new image denoising algorithm that exploits an image's representation in multiple wavelet domains. Besov balls are convex sets of images whose Besov norms are bounded from above by their radii. Projecting an image onto a Besov ball of proper radius corresponds to a type of wavelet shrinkage for image denoising. By defining Besov balls in multiple wavelet domains and projecting onto their intersection using the projection onto convex sets (POCS) algorithm, we obtain an estimate that effectively combines estimates from multiple wavelet domains. While simple, the algorithm provides significant improvement over conventional wavelet shrinkage algorithms based on a single wavelet domain.

We present a framework for maximizing the capacity of symmetric bit-rate communication services dominated by Gaussian crosstalk, in particular, digital subscriber line (DSL) services. We solve for optimal transmit power spectral densities (PSDs) that maximize the joint capacity of same-service users and yield significant gains in bit rates (or performance margins) over current schemes. Our results differ from previous work in that we develop transmit spectra in the presence of self-far-end crosstalk in addition to self-near-end crosstalk, present optimal contiguous spectra for practical modulation schemes, and derive optimal spectra under an additional frequency-domain peak-power constraint. Furthermore, by design, the optimal transmit PSDs are spectrally compatible with existing services on neighboring lines.

A new algorithm for compressing three-dimensional triangular mesh data was used for representing surfaces. The estimation-quantization (EQ) algorithm was applied. EQ was originally designed for still image compression to the normal mesh wavelet coefficient. The EQ algorithm models the wavelet coefficients as a Gaussian random field with slowly varying standard deviation. By designing the quantizers in a rate-distortion optimal fashion, the previously proposed zerotree normal mesh compression algorithm has improved distortion by 0.5 to 1 dB.

Due to inherent factors such as a small and fragmented market and rapid hardware obsolescence, the conventional textbook is inadequate for DSP laboratory education. Freely available open-content materials that enable and promote both local customization and further development by a community of educators offers a fresh approach to lab text development that can surmount these barriers. We overview a joint effort under the aegis of the Connexions Project to develop a large pool of DSP lab modules sufficient to serve as the complete, stand-alone text for several types of DSP lab courses.

Complex wavelet transforms offer the opportunity to perform directional and coherent processing based on the local magnitude and phase of signals and images. Although denoising, segmentation, and image enhancement are significantly improved using complex wavelets, the redundancy of most current transforms hinders their application in compression and related problems. In this paper we introduce a new orthonormal complex wavelet transform with no redundancy for both real- and complex-valued signals. The transform's filter bank features a real low pass filter and two complex high pass filters arranged in a critically sampled three-band structure. Placing symmetry and orthogonality constraints on these filters, we find that each high-pass filter can be factored into a real high pass filter followed by an approximate Hilbert transform filter.

We routinely encounter digital color images that were previously JPEG-compressed. We aim to retrieve the various settings - termed JPEG compression history (CH) - employed during previous JPEG operations. This information is often discarded en-route to the image's current representation. The discrete cosine transform coefficient histograms of previously JPEG-compressed images exhibit near-periodic behavior due to quantization. We propose a statistical approach to exploit this structure and thereby estimate the image's CH. Using simulations, we first demonstrate the accuracy of our estimation. Further, we show that JPEG recompression performed by exploiting the estimated CH strikes an excellent file-size versus distortion tradeoff.

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

A distributed coding technique for images captured from sensors with overlapping fields of view in a sensor network is outlined. First, images from correlated views are roughly registered (relative to a sensor of primary interest) via a low-bandwidth data-sharing method involving image feature points and feature point correspondence. An area of overlap is then identified, and each sensor transmits a low-resolution version of the common image block to the receiver, amortizing the coding cost for that block among the set of sensors. Super-resolution techniques are finally employed at the receiver to reconstruct a high-resolution version of the common block. We discuss the registration and super-resolution techniques used and present examples of each step in the proposed coding process. A numerical analysis illustrating the potential coding benefit follows, and we conclude with a brief discussion of the key issues remaining to be resolved on the path to coder robustness.

We investigate central issues such as invertibility, stability, synchronization, and frequency characteristics for nonlinear wavelet transforms built using the lifting framework. The nonlinearity comes from adaptively choosing between a class of linear predictors within the lifting framework. We also describe how earlier families of nonlinear filter banks can be extended through the use of prediction functions operating on a causal neighborhood of pixels. Preliminary compression results for model and real-world images demonstrate the promise of our techniques.

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

Many wireless systems exploit transmit diversity for more reliable detection of signals at the receiver. To accomplish this, coding is spread across multiple transmit antennas. An example of this is the well known "Alamouti transmit diversity", where a very simple coding scheme across multiple transmit antennas allows systems to attain performance similar to systems with multiple receive antennas. The major drawback is that this system only works when a "flat-fading" model for the channel is assumed; when used in a multipath environment, the system breaks down. Here we show that when the Alamouti code is placed within an OFDM structure, using adjacent frequency bands rather than consecutive symbol intervals, it can asymptotically achieve the same performance in multipath fading as the Alamouti code in flat-fading.

Connexions is a new approach to authoring, teaching, and learning that aims to fully exploit modern information technology. Available free of charge to anyone under open-content and open-source licenses, Connexions offers custom-tailored, current course material, is adaptable to a wide range of learning styles, and encourages students to explore the links among courses and disciplines. In contrast to the traditional process of textbook writing and publishing, Connexions fosters world-wide, cross-institution communities of authors, instructors, and students, who collaboratively and dynamically fashion “modules” from which courses are constructed. We believe the ideas and philosophy embodied by Connexions have the potential to change the very nature of textbook writing and publishing, producing a dynamic, interconnected educational environment that is pedagogically sound, both time and cost efficient, and fun. This paper overviews the philosophy and technology behind Connexions and describes a nascent community developing material for DSP education.

Network traffic exhibits drastically different statistics, ranging from nearly Gaussian marginals and Long range dependence at very large time scales to highly non-Gaussian marginals and multi fractal scaling on small scales. This behavior can be explained by forming two components of the traffic according to the speed of connections, one component absorbing most traffic and being mostly Gaussian, the other constituting virtually all the small scale bursts. Towards a better understanding of this phenomenon, we propose a novel tree-based model which is flexible enough to accommodate Gaussian as well as bursty behavior on different scales in a parsimonious way.

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

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

In many communication systems, including digital subscriber lines, the performance is severely limited by crosstalk interference. Previous work has presented a general framework for designing optimal transmit spectra for crosstalk avoidance. The technique uses the channel, noise, and interference characteristics to setup and solve an optimization problem which maximizes the capacity of neighboring lines, while maintaining spectral compatibility with other services. This joint signaling and optimal power distribution technique yields significant performance gains over conventional fixed spectra in terms of bit-rates and performance margins. In general, the spectra that result from this scheme have both an echo cancelled and frequency division multiplexed region. To ease the analysis, this technique assumed that the echo canceller has perfect echo rejection capability, which in practice is not true. We propose an extension to these techniques, in which we factor the performance of practical echo cancellers into the optimization procedure. When echo rejection is not perfect, as is generally the case, our technique shows significant performance gains over previous techniques. As the performance of the echo canceller increases, our technique converges to the same solution.

This paper reviews the multifractal wavelet model (MWM) and its applications to network traffic modeling and inference. The discovery of the fractal nature of traffic has made new models and analysis tools for traffic essential, since classical Poisson and Markov models do not capture important fractal properties like multiscale variability and burstiness that deleteriously affect performance. Set in the framework of multiplicative cascades, the MWM provides a link to multifractal analysis, a natural tool to characterize burstiness. The simple structure of the MWM enables fast O(N) synthesis of traffic for simulations and a tractable queuing analysis, thus rendering it suitable for real networking applications including end-to-end path modeling.

Multiresolution triangulation meshes are widely used in computer graphics for 3D modeling of shapes. We propose an image representation and processing framework using a multiscale triangulation of the grayscale function. Triangles have the potential of approximating edges better than the blocky structures of tensor-product wavelets. Among the many possible triangulation schemes, normal meshes are natural for efficiently representing singularities in image data, thanks to their adaptivity to the smoothness of the modeled image. Our non-linear, multiscale image decomposition algorithm, based on this subdivision scheme, takes edges into account in a way that is closely related to wedgelets and curvelets. The highly adaptive property of the normal mesh construction provides a very efficient representation of images, which potentially outperforms standard wavelet transforms. We demonstrate the approximation performance of the normal mesh representation through mathematical analyses for simple functions and simulations for real images.

Given a color image that was quantized in some hidden color space (termed compression color space) during previous JPEG compression, we aim to estimate this unknown compression color space from the image. This knowledge is potentially useful for color image enhancement and JPEG re-compression. JPEG quantizes the discrete cosine transform (DCT) coefficients of each color plane independently during compression. Consequently, the DCT coefficients of such a color image conform to a lattice. We exploit this special geometry using the lattice reduction algorithm used in cryptography to estimate the compression color space. Simulations verify that the proposed algorithm yields accurate compression space estimates.

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

We introduce a new image texture segmentation algorithm, HMTseg, based on wavelets and the hidden Markov tree (HMT) model. The HMT is a tree-structured probabilistic graph that captures the statistical properties of the coefficients of the wavelet transform. Since the HMT is particularly well suited to images containing singularities (edges and ridges), it provides a good classifier for distinguishing between textures. Utilizing the inherent tree structure of the wavelet HMT and its fast training and likelihood computation algorithms, we perform texture classification at a range of different scales. We then fuse these multiscale classifications using a Bayesian probabilistic graph to obtain reliable final segmentations. Since HMTseg works on the wavelet transform of the image, it can directly segment wavelet-compressed images without the need for decompression into the space domain. We demonstrate the performance of HMTseg with synthetic, aerial photo, and document image segmentations.

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

The generalized entropies of Renyi inspire new measures for estimating signal information and complexity in the time-frequency plane. When applied to a time-frequency representation (TFR) from Cohen's class or the affine class, the Renyi entropies conform closely to the notion of complexity that we use when visually inspecting time-frequency images. These measures possess several additional interesting and useful properties, such as accounting and cross-component and transformation invariances, that make them natural for time-frequency analysis. This paper comprises a detailed study of the properties and several potential applications of the Renyi entropies, with emphasis on the mathematical foundations for quadratic TFRs. In particular, for the Wigner distribution, we establish that there exist signals for which the measures are not well defined.

We present an efficient method for robustly calculating time-frequency attributes of a signal, including instantaneous mean frequency, bandwidth, and kurtosis. Most current approaches involve a costly intermediate step of computing a (highly oversampled) 2-D bilinear time-frequency representation (TFR), which is then collapsed to the 1-D attribute. Using the principles of hybrid linear/bilinear time-frequency analysis, we propose computing attributes as nonlinear combinations of the (barely oversampled) linear Gabor transform of the signal. The method is both computationally efficient and accurate-it performs as well as the best bilinear techniques based on adaptive TFRs. To illustrate, we calculate an attribute of a seismic cross-section.

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

The discrete wavelet transform (DWT) gives a compact multiscale representation of signals and provides a hierarchical structure for signal processing. It has been assumed the DWT can fairly well decorrelate real-world signals. However a residual dependency structure still remains between wavelet coefficients. It has been observed magnitudes of wavelet coefficients are highly correlated, both across the scale and at neighboring spatial locations. In this paper we present a wavelet folding technique, which folds wavelet coefficients across the scale and removes the across-the-scale dependence to a larger extent. It produces an even more compact signal representation and the energy is more concentrated in a few large coefficients. It has a great potential in applications such as image compression.

A real-time imaging system based on terahertz (THz) time-domain spectroscopy has been demonstrated. This technique offers a range of unique imaging modalities due to the broad bandwidth, sub-picosecond duration, and phase-sensitive detection of the THz pulses. This paper provides an introduction of the state-of-the art in THz imaging. It also focuses on expanding the potential of this new and exciting field through two major efforts. The first concentrates on improving the experimental sensitivity of the system. We are exploring an interferometric arrangement to provide a background-free reflection imaging geometry. The second applies novel digital signal processing algorithms to extract useful information from the THz pulses. The possibility exists to combine spectroscopic characterization and/or identification with pixel-by-pixel imaging.

In this paper, we demonstrate based on the linear model of Kite et al. (1997, 2000) that inverse halftoning is equivalent to the well-studied problem of deconvolution in the presence of colored noise. We propose the use of the simple and elegant wavelet-vaguelette deconvolution (WVD) algorithm to perform the inverse halftoning. Unlike previous wavelet-based algorithms, our method is model-based; hence it is adapted to different error diffusion halftoning techniques. Our inverse halftoning algorithm consists of inverting the convolution operator followed by denoising in the wavelet domain. For signals in a Besov space, our algorithm possesses asymptotically (as the number of samples/spl rarr//spl infin/) near-optimal rates of error decay. Hence for images in a Besov space, it is impossible to improve significantly on the inverse halftoning performance of the WVD algorithm at high resolutions. Using simulations, we verify that our algorithm outperforms or matches the performances of the best published inverse halftoning techniques in the mean square error (MSE) sense and also provides excellent visual performance.

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

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 an unsure footing. In this paper, we study these two issues by introducing a multiscale traffic model and a novel multiscale approach to queuing analysis. The multifractal wavelet model (MWM) is a multiplicative, wavelet-based model that captures the positivity, LRD, and "spikiness" of non-Gaussian traffic. Using a binary tree, the model synthesizes an N-point data set with only O(N) computations. Leveraging the tree structure of the model, we derive a multiscale queuing analysis that provides a simple closed form approximation to the tail queue probability, valid for any given buffer size. The analysis is applicable not only to the MWM but to tree-based models in general, including fractional Gaussian noise. Simulated queuing experiments demonstrate the accuracy of the MWM for matching real data traces and the precision of our theoretical queuing formula. Thus, the MWM is useful not only for fast synthesis of data for simulation purposes but also for applications requiring accurate queuing formulas such as call admission control. 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.

We link concepts from nonuniform sampling, smoothness function spaces, interpolation, and denoising to derive a suite of multiscale, maximum-smoothness interpolation algorithms. We formulate the interpolation problem as the optimization of finding the signal that matches the given samples with smallest norm in a function smoothness space. For signals in the Besov space B/sub q//sup /spl alpha// (L/sub p/), the optimization corresponds to convex programming in the wavelet domain; for signals in the Sobolev space W/sup /spl alpha//(L/sub 2/), the optimization reduces to a simple weighted least-squares problem. An optional wavelet shrinkage regularization step makes the algorithm suitable for even noisy sample data, unlike classical approaches such as bandlimited and spline interpolation.

In this paper, we propose a new approach to wavelet-based deconvolution. Roughly speaking, the algorithm comprises Fourier-domain system inversion followed by wavelet-domain noise suppression. Our approach subsumes a number of other wavelet-based deconvolution methods. In contrast to other wavelet-based approaches, however, we employ a regularized inverse filter, which allows the algorithm to operate even when the inverse system is ill-conditioned or non-invertible. Using a mean-square-error metric, we strike an optimal balance between Fourier-domain and wavelet-domain regularization. The result is a fast deconvolution algorithm ideally suited to signals and images with edges and other singularities. In simulations with real data, the algorithm outperforms the LTI Wiener filter and other wavelet-based deconvolution algorithms in terms of both visual quality and MSE performance.

Wavelet-based image denoising algorithm depends upon the energy compaction property of wavelet transforms. However, for many real-world images, we cannot expect good energy compaction in a single wavelet domain, because most real-world images consist of components of a variety of smoothness. We can relieve this problem by using multiple wavelet bases to match different characteristics of images. In this paper, we propose a novel image denoising algorithm that uses multiple wavelet bases. By establishing a new relationship between the deterministic Besov space theory and the wavelet-domain statistical models, we generalize the Besov theory for finite sampled data. After defining convex sets in Besov spaces that contain the true image, we obtain an estimate of the true image by the method of projection onto convex sets. The algorithm outperforms existing multiple wavelet basis denoising algorithms; in particular, it shows excellent performance at low signal-to-noise ratios.

We propose a hybrid approach to wavelet-based image deconvolution that comprises Fourier-domain system inversion followed by wavelet-domain noise suppression. In contrast to conventional wavelet-based deconvolution approaches, the algorithm employs a regularized inverse filter, which allows it to operate even when the system is non-invertible. Using a mean-square-error metric, we strike an optimal balance between Fourier-domain regularization that is matched to the system and wavelet-domain regularization that is matched to the signal. Theoretical analysis reveals that the optimal balance is determined by economics of the input signal wavelet representation and the operator structure. The resultant algorithm is fast, O(N log/sub 2//sup 2/ N) where N denotes the number of samples, and is well-suited to data with spatially-localized phenomena such as edges. In addition to enjoying asymptotically near-optimal rates of error decay for some systems, the algorithm also achieves excellent performance at fixed data lengths. In simulations with real data, the algorithm outperforms the conventional LTI Wiener filter and other wavelet-based deconvolution algorithms in terms of both visual quality and MSE performance.

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

In this paper, we develop a simple and powerful multiscale model for the synthesis of nonGaussian, long-range dependent (LRD) network traffic. Although wavelets effectively decorrelate LRD data, wavelet-based models have generally been restricted by a Gaussianity assumption that can be unrealistic for traffic. Using a multiplicative superstructure on top of the Haar wavelet transform, we exploit the decorrelating properties of wavelets while simultaneously capturing the positivity and "spikiness" of nonGaussian traffic. This leads to a swift O(N) algorithm for fitting and synthesizing N-point data sets. The resulting model belongs to the class of multifractal cascades, a set of processes with rich statistical properties. We elucidate our model's ability to capture the covariance structure of real data and then fit it to real traffic traces. Queueing experiments demonstrate the accuracy of the model for matching real data. Our results indicate that the nonGaussian nature of traffic has a significant effect on queuing.

Many imaging systems rely on photon detection as the basis of image formation. One of the major sources of error in these systems is Poisson noise due to the quantum nature of the photon detection process. Unlike additive Gaussian white noise, the variance of Poisson noise is proportional to the underlying signal intensity, and consequently separating signal from noise is a very difficult task. In this paper, we perform a novel gedankenexperiment to devise a new wavelet-domain filtering procedure for noise removal in photon imaging systems. The filter adapts to both the signal and the noise, and balances the trade-off between noise removal and excessive smoothing of image details. Designed using the statistical method of cross-validation, the filter is simultaneously optimal in a small-sample predictive sum of squares sense and asymptotically optimal in the mean-square-error sense. The filtering procedure has a simple interpretation as a joint edge detection/estimation process. Moreover, we derive an efficient algorithm for performing the filtering that has the same order of complexity as the fast wavelet transform itself. The performance of the new filter is assessed with simulated data experiments and tested with actual nuclear medicine imagery.

We develop a new multiscale modeling framework for characterizing positive-valued data with long-range-dependent correlations (1/f noise). 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 study both the second-order and multifractal properties of the model, the latter after a tutorial overview of multifractal analysis. We derive a scheme for matching the model to real data observations and, to demonstrate its effectiveness, apply the model to network traffic synthesis. The flexibility and accuracy of the model and fitting procedure result in a close fit to the real data statistics (variance-time plots and moment scaling) and queuing behavior. Although for illustrative purposes we focus on applications in network traffic modeling, the multifractal wavelet model could be useful in a number of other areas involving positive data, including image processing, finance, and geophysics.

Summary form only given. Image compression relies on efficient representations of images, and within smooth image regions, the wavelet transform provides such a representation. However, near edges, wavelet coefficients decay slowly and are expensive to code. We focus on improving the transform by incorporating adaptivity. Construction of nonlinear filter banks has been discussed, but the question of how to utilize the nonlinearities remained. We answer this question by describing our transform via lifting. Lifting provides a spatial domain framework for the wavelet transform. In the lifting formalism, wavelet coefficients are seen as prediction residuals from a linear prediction operation. Wavelet coefficients are large near edges because the linear predictors are built to interpolate low order polynomials. Our goal is to avoid this problem by adapting the predictor based on local image properties. In smooth regions of the image, we use high order polynomial predictors. We adaptively reduce the prediction order to avoid attempting to predict values across discontinuities.

This paper develops two new adaptive wavelet transforms based on the lifting scheme. The lifting construction exploits a spatial-domain, prediction-error interpretation of the wavelet transform and provides a powerful framework for designing customized transforms. We use the lifting construction to adaptively tune a wavelet transform to a desired signal by optimizing data-based prediction error criteria. The performances of the new transforms are compared to existing wavelet transforms, and applications to signal denoising are investigated.

Wavelet-domain hidden Markov models (HMMs) are a potent new tool for modeling the statistical properties of wavelet transforms. In addition to characterizing the statistics of individual wavelet coefficients, HMMs capture the salient interactions between wavelet coefficients. However, as we model an increasing number of wavelet coefficient interactions, HMM-based signal processing becomes increasingly complicated. In this paper, we propose a new approach to HMMs based on the notion of context. By modeling wavelet coefficient inter-dependencies via contexts, we retain the approximation capabilities of HMMs, yet substantially reduce their complexity. To illustrate the power of this approach, we develop new algorithms for signal estimation and for efficient synthesis of nonGaussian, long-range-dependent network traffic.

In this correspondence, we propose a general framework for studying a class of weighted highpass filters. Our framework, based on a multiscale signal decomposition, allows us to study a wide class of filters and to assess the merits of each. We derive an automatic procedure to tune a filter to the local structure of the image under consideration. The entire algorithm is fully automatic and requires no parameter specification from the user. Several simulations demonstrate the efficacy of the proposed algorithm.

Current wavelet-based statistical signal and image processing techniques such as shrinkage and filtering treat the wavelet coefficients as though they were statistically independent. This assumption is unrealistic; considering the statistical dependencies between wavelet coefficients can yield substantial performance improvements. We develop a new framework for wavelet-based signal processing that employs hidden Markov models to characterize the dependencies between wavelet coefficients. To illustrate the power of the new framework, we derive a new algorithm for signal estimation in nonGaussian noise.

When applied to continuous-time observations, type-based detection strategies are limited by the necessity to crudely quantize each sample. To alleviate this problem, we smooth the types for both the training and observation data with a linear filter. This post-processing improves the detector performance significantly (error probabilities decrease by over a factor of three) without incurring a significant computational penalty. However this improvement depends on the amplitude distribution and on the quantizer's characteristics.

Nonlinearities are often encountered in the analysis and processing of real-world signals. This paper develops new transformations for nonlinear signal processing. The theory of tensor norms is employed to show that wavelets provide an optimal basis for the new transformations. The results are applied to Volterra kernel identification.

We define a new set of tools for time-varying spectral analysis: the pseudo affine Wigner distributions. Based on the affine Wigner distributions of J. and P. Bertrand (1992), these new time-frequency distributions support efficient online operation at the same computational cost as the continuous wavelet transform. Moreover, they take advantage of the proportional bandwidth smoothing inherent in the sliding structure of their implementation to suppress cumbersome interference components. To formalize their place within the echelon of the affine class of time-frequency distributions, we extend the definition of this class and introduce other natural generators.

We consider the design of kernels for time-frequency distributions through the phase, rather than amplitude, response. While phase kernels do not attenuate troublesome cross-components, they can translate them in the time-frequency plane. In contrast to previous work on phase kernels that concentrated on placing the cross-components on top of the auto-components, we set up a "don't care" region and place the cross-components there. The close connections between optimal allpass kernels and optimal lowpass kernels provide valuable insight into signal-dependent time-frequency analysis.

By representing signals in terms of several physical quantities simultaneously, joint distribution functions can reveal signal features that remain hidden from other methods of analysis. Cohen (1966, 1995) has proposed a construction for joint distributions of arbitrary physical quantities, in direct generalization of joint time-frequency representations. Actually, this method encompasses two approaches: one based on operator correspondences and one based on weighting kernels. The literature has emphasized the kernel method due to its ease of analysis; however, its simplicity comes at a price. We use a simple example to demonstrate that the kernel method cannot generate an possible bilinear joint distributions. Our results suggest that the relationship between the operator method and the kernel method merits closer scrutiny.

We propose a straightforward characterization of all quadratic time-frequency representations covariant to an important class of unitary signal transforms (namely, those having two continuous-valued parameters and an underlying group structure). Thanks to a fundamental theorem from the theory of Lie groups, we can describe these representations simply in terms of unitary transformations of the well-known Cohen's and affine classes.

Using the pseudo-Wigner time-frequency distribution as a guide, we derive two new time-scale representations: the pseudo-Bertrand and the smoothed pseudo-Bertrand distributions. Unlike the Bertrand distribution, these representations support efficient online operation at the same computational cost as the continuous wavelet transform. Moreover, they take advantage of the affine smoothing inherent in the sliding structure of their implementation to suppress cumbersome interference components.

Teleoperation continues to be a primary control mode in robotics applications, particularly for robots with complex hands. This paper details a novel method of teleoperation of complex anthropomorphic robotic hands: converting the myoelectric signal (generated by the operator's muscles during movement) into robot commands replicating the motion. Myoelectric prosthetic hands have used this user interface for over two decades; however, the feasibility of using this approach for commanding more than one degree-of-freedom, as in the pincher type grip in current myoelectric hands, has been in question. The research described in this paper addresses myoelectric control of NASA/Johnson Space Center's sixteen degree-of-freedom Utah/MIT Dextrous Hand for two grasping (key and chuck) options and three thumb motions (abduction, extension, and flexion). We discuss myoelectric signal processing approaches, data collection apparatus, and a realtime teleoperation implementation. We also present results in realtime discrimination of key and chuck grasps and offline discrimination of thumb motions. Our results include a 90% correct grasp selection rate and an 87% correct thumb motion selection, both using the myoelectric spectrum.

Cohen (1966, 1995) has proposed a method for constructing joint distributions of arbitrary physical quantities, in direct generalization of joint time-frequency representations. We investigate the covariance properties of this procedure and caution that in its present form it cannot generate all possible distributions. Using group theory, we extend Cohen's construction to a more general form that can be customized to satisfy specific marginal and covariance requirements.

There has been considerable interest in the problem of joint representations for variables other than time and frequency. We compare the methods of Cohen (1991) and of Baraniuk and Jones (see Proc. IEEE Int. Conf. Acoust., Speech Signal Processing, ICASSP '93, p.320-323, vol.III) and show their equivalence for variables that have the same commutator as time and frequency. In addition, we report the following very general result. All pairs of variables connected by a unitary transformation have joint distributions that are functionally equivalent.>

Given a unitary operator A representing a physical quantity of interest, we employ concepts from group representation theory to define two natural signal energy densities for A. The first is invariant to A and proves useful when the effect of A is to be ignored; the second is covariant to A and measures the "A" content of signals. The construction is quite general and is also easily extended to the multi-operator case, which generalizes previously derived joint densities such as the time-frequency and time-scale distributions.>

Many functions have been proposed for estimating signal information content and complexity on the time-frequency plane, including moment-based measures such as the time-bandwidth product and the Shannon and Renyi(see 4th Berkeley Symp. Math., Stat., Prob., vol.1) entropies. When applied to a time-frequency representation from Cohen's (1989) class, the Renyi entropy conforms closely to the visually based notion of complexity that we use when inspecting time-frequency images. A detailed discussion reveals many of the desirable properties of the Renyi information measure for both deterministic and random signals.>

The high noise sensitivity of the Wigner distribution makes smoothing a necessity for producing readable time-frequency images of noise corrupted signals. Since linear smoothing suppresses noise at the expense of considerable smearing of the signal components, the author explores two nonlinear denoising techniques based on soft-thresholding in an orthonormal basis representation. Soft-thresholding provides considerable noise reduction without greatly impairing the time-frequency resolution of the denoised distribution.>

A new class of signal analysis tools that generalizes the popular wavelet and short-time Fourier transforms is introduced. The class allows skews and rotations of the analyzing wavelet in the time-frequency plane, in addition to the time and frequency translations and scalings used by conventional transforms. In addition to providing a unifying framework for studying existing time-frequency representations, the general class provides a systematic method for designing new representations with properties useful for certain types of signals.>

An optimization formulation for designing signal-dependent kernels that are based on radially Gaussian functions is presented. The method is based on optimality criteria and is not ad hoc. The procedure is automatic. The optimization criteria are formulated so that the resulting time-frequency distribution (TFD) is insensitive to the time scale and orientation of the signal in time-frequency. Examples demonstrate that the optimal-kernel TFD offers excellent performance for a larger class of signals than any current fixed-kernel representation. The technique performs well in the presence of substantial additive noise, which suggests that it may prove useful for automatic detection of unknown signals in noise. The cost of this technique is only a few times greater than that of the fixed-kernel methods and the 1/0 optimal kernel method.>