The recent success of neural networks in pattern recognition and classification problems suggests that they possess qualities distinct from other more classical classifiers, such as SVMs or boosting classifiers. This paper studies the performance of plug-in classifiers based on neural networks in a binary classification setting as measured by their excess risks. Compared to the typical settings imposed in the literature, we consider a more general scenario that resembles actual practice in two respects: first, the function class to be approximated includes the Barron functions as a proper subset, and second, the neural network classifier constructed is the minimizer of a surrogate loss for which the gradient descent-based numerical optimizations can be easily applied. While the class of distributions we consider is quite large that optimal rates cannot be faster thann–1/3, it is a regime in which dimension-free rates are possible, and approximation power of neural networks can be taken advantage of. In particular, we analyze the estimation and approximation properties of neural networks to obtain a dimension-free, uniform rate of convergence for the excess risk. Finally, we show that the rate obtained is, in fact, minimax optimal up to a logarithmic factor, and the minimax lower bound shows the effect of the margin assumption in this regime.

Contextual bandit algorithms are essential for solving real-world decision making problems. In practice, collecting a contextual bandit's feedback from different domains may involve different costs. For example, measuring drug reaction from mice (as a source domain) and humans (as a target domain). Unfortunately, adapting a contextual bandit algorithm from a source domain to a target domain with distribution shift still remains a major challenge and largely unexplored. In this paper, we introduce the first general domain adaptation method for contextual bandits. Our approach learns a bandit model for the target domain by collecting feedback from the source domain. Our theoretical analysis shows that our algorithm maintains a sub-linear regret bound even adapting across domains. Empirical results show that our approach outperforms the state-of-the-art contextual bandit algorithms on real-world datasets. Code will soon be available at https://github.com/Wang-ML-Lab/DABand.

This paper introduces a novel kernel-based formulation of the Equalized Odds (EO) criterion, denoted as $\operatorname{EO}_k$, for fair representation learning (FRL) in supervised settings. The central goal of FRL is to mitigate discrimination regarding a sensitive attribute $S$ while preserving prediction accuracy for the target variable $Y$. Our proposed criterion enables a rigorous and interpretable quantification of three core fairness objectives: independence ($\widehat{Y} \perp S$), separation—also known as equalized odds ($\widehat{Y} \perp S \mid Y$), and calibration ($Y \perp S \mid \widehat{Y}$). Under both unbiased ($Y \perp S$) and biased ($Y \not \perp S$) conditions, we show that $\operatorname{EO}_k$ satisfies both independence and separation in the former, and uniquely preserves predictive accuracy while lower bounding independence and calibration in the latter, thereby offering a unified analytical characterization of the tradeoffs among these fairness criteria. We further define the empirical counterpart, $\widehat{\operatorname{EO}}_k$, a kernel-based statistic that can be computed in quadratic time, with linear-time approximations also available. A concentration inequality for $\widehat{\operatorname{EO}}_k$ is derived, providing performance guarantees and error bounds, which serve as practical certificates of fairness compliance. While our focus is on theoretical development, the results lay essential groundwork for principled and provably fair algorithmic design in future empirical studies.

Diffusion models have made significant advancements in recent years. However, their performance often deteriorates when trained or fine-tuned on imbalanced datasets. This degradation is largely due to the disproportionate representation of majority and minority data in image-text pairs. In this paper, we propose a general fine-tuning approach, dubbed PoGDiff, to address this challenge. Rather than directly minimizing the KL divergence between the predicted and ground-truth distributions, PoGDiff replaces the ground-truth distribution with a Product of Gaussians (PoG), which is constructed by combining the original ground-truth targets with the predicted distribution conditioned on a neighboring text embedding. Experiments on real-world datasets demonstrate that our method effectively addresses the imbalance problem in diffusion models, improving both generation accuracy and quality.

In this paper, we prove the universal consistency of wide and deep ReLU neural network classifiers. We also give sufficient conditions for a class of probability measures for which classifiers based on neural networks achieve minimax optimal rates of convergence. The result applies to a wide range of known function classes. In particular, while most previous works impose explicit smoothness assumptions on the regression function, our framework encompasses more general settings. The proposed neural networks are either the minimizers of the $0$-$1$ loss that exhibit a benign overfitting behavior.

Adversarial training can achieve robustness against adversarial perturbations and has been widely used in machine-learning models. This paper delivers a non-asymptotic consistency analysis of the adversarial training procedure under $\ell_\infty$-perturbation in high-dimensional linear regression. It will be shown that, under the restricted eigenvalue condition, the associated convergence rate of prediction error can achieve the minimax rate up to a logarithmic factor in the high-dimensional linear regression on the class of sparse parameters. Additionally, the group adversarial training procedure is analyzed. Compared with classic adversarial training, it will be proved that the group adversarial training procedure enjoys a better prediction error upper bound under certain group-sparsity patterns.

We propose an adjusted Wasserstein distributionally robust estimator---based on a nonlinear transformation of the Wasserstein distributionally robust (WDRO) estimator in statistical learning. The classic WDRO estimator is asymptotically biased, while our adjusted WDRO estimator is asymptotically unbiased, resulting in a smaller asymptotic mean squared error. Further, under certain conditions, our proposed adjustment technique provides a general principle to de-bias asymptotically biased estimators. Specifically, we will investigate how the adjusted WDRO estimator is developed in the generalized linear model, including logistic regression, linear regression, and Poisson regression. Numerical experiments demonstrate the favorable practical performance of the adjusted estimator over the classic one.

This paper studies the binary classification of unbounded data from ${\mathbb R}^d$ generated under Gaussian Mixture Models (GMMs) using deep ReLU neural networks. We obtain — for the first time — non-asymptotic upper bounds and convergence rates of the excess risk (excess misclassification error) for the classification without restrictions on model parameters. While the majority of existing generalization analysis of classification algorithms relies on a bounded domain, we consider an unbounded domain by leveraging the analyticity and fast decay of Gaussian distributions. To facilitate our analysis, we give a novel approximation error bound for general analytic functions using ReLU networks, which may be of independent interest. Gaussian distributions can be adopted nicely to model data arising in applications, e.g., speeches, images, and texts; our results provide a theoretical verification of the observed efficiency of deep neural networks in practical classification problems.

This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetilde{\mathcal{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$, where $n$ is the problem size and $\epsilon$ is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is $\widetilde{\mathcal{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $\widetilde{\mathcal{O}}({n^2}/{\epsilon})$ for solving OT.

Given a sequence of observable variables $\{(x_1, y_1), \ldots, (x_n, y_n)\}$, the conformal prediction method estimates a confidence set for $y_{n+1}$ given $x_{n+1}$ that is valid for any finite sample size by merely assuming that the joint distribution of the data is permutation invariant. Although attractive, computing such a set is computationally infeasible in most regression problems. Indeed, in these cases, the unknown variable $y_{n+1}$ can take an infinite number of possible candidate values, and generating conformal sets requires retraining a predictive model for each candidate. In this paper, we focus on a sparse linear model with only a subset of variables for prediction and use numerical continuation techniques to approximate the solution path efficiently. The critical property we exploit is that the set of selected variables is invariant under a small perturbation of the input data. Therefore, it is sufficient to enumerate and refit the model only at the change points of the set of active features and smoothly interpolate the rest of the solution via a Predictor-Corrector mechanism. We show how our path-following algorithm accurately approximates conformal prediction sets and illustrate its performance using synthetic and real data examples.

We study the Stochastic Gradient Descent (SGD) algorithm in nonparametric statistics: kernel regression in particular. The directional bias property of SGD, which is known in the linear regression setting, is generalized to the kernel regression. More specifically, we prove that SGD with moderate and annealing step-size converges along the direction of the eigenvector that corresponds to the largest eigenvalue of the Gram matrix. In addition, the Gradient Descent (GD) with a moderate or small step-size converges along the direction that corresponds to the smallest eigenvalue. These facts are referred to as the directional bias properties; they may interpret how an SGD-computed estimator has a potentially smaller generalization error than a GD-computed estimator. The application of our theory is demonstrated by simulation studies and a case study that is based on the FashionMNIST dataset.

In machine learning and statistical data analysis, we often run into objective function that is a summation: the number of terms in the summation possibly is equal to the sample size, which can be enormous. In such a setting, the stochastic mirror descent (SMD) algorithm is a numerically efficient method—each iteration involving a very small subset of the data. The variance reduction version of SMD (VRSMD) can further improve SMD by inducing faster convergence. On the other hand, algorithms such as gradient descent and stochastic gradient descent have the implicit regularization property that leads to better performance in terms of the generalization errors. Little is known on whether such a property holds for VRSMD. We prove here that the discrete VRSMD estimator sequence converges to the minimum mirror interpolant in the linear regression. This establishes the implicit regularization property for VRSMD. As an application of the above result, we derive a model estimation accuracy result in the setting when the true model is sparse. We use numerical examples to illustrate the empirical power of VRSMD.

In image detection, one problem is to test whether the set, though mainly consisting of uniformly scattered points, also contains a small fraction of points sampled from some (a priori unknown) curve, for example, a curve with Cα-norm bounded by β. One approach is to analyze the data by counting membership in multiscale multianisotropic strips, which involves an algorithm that delves into the length of the path connecting many consecutive “significant” nodes. In this paper, we develop the mathematical formalism of this algorithm and analyze the statistical property of the length of the longest significant run. The rate of convergence is derived. Using percolation theory and random graph theory, we present a novel probabilistic model named, pseudo-tree model. Based on the asymptotic results for the pseudo-tree model, we further study the length of the longest significant run in an “inflating” Bernoulli net. We find that the probability parameter p of significant node plays an important role: there is a threshold pc, such that in the cases of pcand p > pc, very different asymptotic behaviors of the length of the significant runs are observed. We apply our results to the detection of an underlying curvilinear feature and prove that the test based on our proposed longest run theory is asymptotically powerful.

Most existing patch-based image denoising algorithms filter overlapping image patches and aggregate multiple estimates for the same pixel via weighting. Current weighting approaches always assume the restored estimates as independent random variables, which is inconsistent with the reality. In this letter, we analyze the correlation among the estimates and propose a bias-variance model to estimate the Mean Squared Error (MSE) under various weights. The new model exploits the overlapping information of the patches; it then utilizes the optimization to try to minimize the estimated MSE. Under this model, we propose a new weighting approach based on Quadratic Programming (QP), which can be embedded into various denoising algorithms. Experimental results show that the Peak Signal to Noise Ratio (PSNR) of algorithms like K-SVD and EPLL can be improved by around 0.1 dB under a range of noise levels. This improvement is promising, since it is gained independent to which image model is used, especially when the gain from designing new image models becomes less and less.

In dimensional inspection using coordinate measuring machines (CMMs), the following issues are critical to achieve accurate inspection while minimizing the cost and time: 1) How can we select the sampling positions of the measurements so that we can get as much information from a limited number of samples as possible and 2) given the limited number of measurements, how can we assess the form error so that one can reliably decide whether the product is acceptable? To address these problems, we propose a wavelet-based model that takes advantage of the fact that the Lipschitz regularity holds for the CMM data. Under the framework of the proposed model, we derive the optimal sampling positions and propose a systematic procedure to estimate the form error given the limited number of sampled points. The proposed method is validated using both synthetic and real CMM data sets for straightness measurements. The comparison with other existing methods demonstrates the effectiveness of our method.

Temporal psychovisual modulation (TPVM) is a newly proposed information display paradigm, which can be implemented by nonnegative matrix factorization (NMF) with additional upper bound constraints on the variables. In this paper, we study all the state-of-the-art algorithms in NMF, extend them to incorporate the upper bounds and discuss their potential use in TPVM. By comparing all the NMF algorithms with their extended versions, we find that: 1) the factorization error of the truncated alternating least squares algorithm always fluctuates throughout the iterations, 2) the alternating nonnegative least squares based algorithms may slow down dramatically under the upper bound constraints, and 3) the hierarchical alternating least squares (HALS) algorithm converges the fastest and its final factorization error is often the smallest among all the algorithms. Based on the experimental results of the HALS, we propose a guideline of determining the parameter setting of TPVM, that is, the number of viewers to support and the scaling factor for adjusting the light intensity of the images formed by TPVM. This paper will facilitate the applications of TPVM.

Expected Patch Log Likelihood (EPLL) framework using Gaussian Mixture Model (GMM) prior for image restoration was recently proposed with its performance comparable to the state-of-the-art algorithms. However, EPLL uses generic prior trained from offline image patches, which may not correctly represent statistics of the current image patches. In this paper, we extend the EPLL framework to an adaptive one, named A-EPLL, which not only concerns the likelihood of restored patches, but also trains the GMM to fit for the degraded image. To efficiently estimate GMM parameters in A-EPLL framework, we improve a recent Expectation-Maximization (EM) algorithm by exploiting specific structures of GMM from image patches, like Gaussian Scale Models. Experiment results show that A-EPLL outperforms the original EPLL significantly on several image restoration problems, like inpainting, denoising and deblurring.

Dimensional integrity has a significant impact on the quality of the final products in multistation assembly processes. A large body of research work in fault diagnosis has been proposed to identify the root causes of the large dimensional variations on products. These methods are based on a linear relationship between the dimensional measurements of the products and the possible process errors, and assume that the number of measurements is greater than that of process errors. However, in practice, the number of measurements is often less than that of process errors due to economical considerations. This brings a substantial challenge to the fault diagnosis in multistation assembly processes since the problem becomes solving an underdetermined system. In order to tackle this challenge, a fault diagnosis methodology is proposed by integrating the state space model with the enhanced relevance vector machine (RVM) to identify the process faults through the sparse estimate of the variance change of the process errors. The results of case studies demonstrate that the proposed methodology can identify process faults successfully.

In this paper we have proposed and designed FindingHuMo (Finding Human Motion), a real-time user tracking system for Smart Environments. FindingHuMo can perform device-free tracking of multiple (unknown and variable number of) users in the Hallway Environments, just from non-invasive and anonymous (not user specific) binary motion sensor data stream. The significance of our designed system are as follows: (a) fast tracking of individual targets from binary motion data stream from a static wireless sensor network in the infrastructure. This needs to resolve unreliable node sequences, system noise and path ambiguity, (b) Scaling for multi-user tracking where user motion trajectories may crossover with each other in all possible ways. This needs to resolve path ambiguity to isolate overlapping trajectories, FindingHumo applies the following techniques on the collected motion data stream: (i) a proposed motion data driven adaptive order Hidden Markov Model with Viterbi decoding (called Adaptive-HMM), and then (ii) an innovative path disambiguation algorithm (called CPDA). Using this methodology the system accurately detects and isolates motion trajectories of individual users. The system performance is illustrated with results from real-time system deployment experience in a Smart Environment.

Image denoising plays a fundamental role in many image processing applications. Utilizing sparse representation and nonlocal averaging together is such a successful framework that leads to considerable progress in denoising. Almost all the newly proposed denoising algorithms are built base on it, different in detailed implementation, and the denoising performance seems converging. What is the denoising bound of this framework turns into a key question. In this paper, we assume all the possible algorithms under the framework can be approximated by a fixed two steps denoising process with different parameters. Step one cluster geometric similar image patches into groups so that patches within each group could be sparse represented under the basis of the group. Step two use the atoms of the group basis and radiometric similar patches of each patch for non-local averaging. The parameters of the process are the cluster number, the atoms and the number of radiometric similar patches for estimating each patch. Finally, the bound is derived as the minimum denoising error of all the possible parameters. Comparing with previous bounds, the new one is image specific and more practical. Experiment results show that there still exists room to improve the denoising performance for natural images.

Sparse signal representation based on overcomplete dictionaries has recently been extensively investigated, rendering the state-of-the-art results in signal, image and video processing. We propose a novel dictionary learning algorithm-the PK-SVD algorithm-which assumes prior probabilities on the dictionary atoms and learns a sparse dictionary under a popularity-based model. The prior distribution brings the flexibility that is desirable in applications. We examine our algorithm in both synthetic tests and image denoising experiments.

Auditory is a convenient and efficient way for Human-Robot Interaction, however implementing a sound source localization system based on TDOA method encounters many problems, such as noise of real environments, and resolution of nonlinear equations, switch between far field and near field and lack of microphones for geometric positioning localization method. In this paper, a new spectral weighting GCC-PHAT method is proposed to deal with noise. Furthermore, the time difference feature of sound source and its spatial distribution are analyzed. Based on prosperities of the distribution, a space grid matching (SGM) algorithm is proposed for localization step, which handles those problems that geometric positioning method faces effectively. Decision tree and valid feature detection algorithm are also proposed to reduce computational complexity and improve performance. Experiments are achieved in real environments on a mobile robot platform, in which 2016 sets of speech data are tested using four microphones in 3D space. More than 95% azimuth localization rate with error less than 5 degrees and approximate 90% horizontal distance localization rate are obtained.

In this paper we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several incremental algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning A* (LPA*) algorithm. Although, in most cases, the LPA* algorithm requires a relatively small number of updates, in some other cases the amount of work required by the LPA* to find the optimal path can be overwhelming. To address this issue, in this paper we propose an extension of the baseline LPA* algorithm, by making efficient use of a multiscale representation of the environment.

Path-planning (equivalently, path-finding) problems are fundamental in many applications, such as transportation, VLSI design, robot navigation, and many more. In this paper, we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning algorithm. The algorithm is an incremental search algorithm that replans the path when there are changes in the environment. In numerical experiments, however, it was observed that the performance of is sensitive in the number of vertex expansions required to update the graph when an edge weight value changes or when a vertex is added or deleted. Although, in most cases, the classical requires a relatively small number of updates, in some other cases the amount of work required by the to find the optimal path can be overwhelming. To address this issue, in this paper, we propose an extension of the baseline algorithm, by making efficient use of a multiscale representation of the environment. This multiscale representation allows one to quickly localize the changed edges, and subsequently update the priority queue efficiently. This incremental multiscale ( for short) algorithm leads to an improvement both in terms of robustness and computational complexity-in the worst case-when compared to the classical . Numerical experiments validate the aforementioned claims.

We propose a novel image denoising approach, which is based on exploring an underlying (nonlinear) lowdimensional manifold. Using local tangent space alignment (LTSA), we 'learn' such a manifold, which approximates the image content effectively. The denoising is performed by minimizing a newly defined objective function, which is a sum of two terms: (a) the difference between the noisy image and the denoised image, (b) the distance from the image patch to the manifold. We extend the LTSA method from manifold learning to denoising. We introduce the local dimension concept that leads to adaptivity to different kind of image patches, e.g. flat patches having lower dimension. We also plug in a basic denoising stage to estimate the local coordinate more accurately. It is found that the proposed method is competitive: its performance surpasses the K-SVD denoising method.

We study the convergence and the rate of convergence of a local manifold learning algorithm: LTSA [13]. The main technical tool is the perturbation analysis on the linear invariant subspace that corresponds to the solution of LTSA. We derive a worst-case upper bound of errors for LTSA which naturally leads to a convergence result. We then derive the rate of convergence for LTSA in a special case.

A frontier-based tree-pruning algorithm (FBP) is proposed. The new method has an order of computational complexity comparable to cost-complexity pruning (CCP). Regarding tree pruning, it provides a full spectrum of information: namely, (1) given the value of the penalization parameter λ, it gives the decision tree specified by the complexity-penalization approach; (2) given the size of a decision tree, it provides the range of the penalization parameter λ, within which the complexity-penalization approach renders this tree size; (3) it finds the tree sizes that are inadmissible—no matter what the value of the penalty parameter is, the resulting tree based on a complexity-penalization framework will never have these sizes. Simulations on real data sets reveal a “surprise:” in the complexity-penalization approach, most of the tree sizes are inadmissible. FBP facilitates a more faithful implementation of cross validation (CV), which is favored by simulations. Using FBP, a stability analysis of CV is proposed.

The multiple measurement vector (MMV), a newly emerged problem in sparse representation in an over-complete dictionary motivated by a neuro-magnetic inverse problem that arises in magnetoencephalography (MEG) - a modality for imaging the possible activation regions in the brain, poses new challenges. Efficient methods have been designed to search for sparse representations; however, we have not seen substantial development in the theoretical analysis, considering what has been done in a simpler case - single measurement vector (SMV) - in which many theoretical results are known. This paper extends the known results of SMV to MMV. Our theoretical results show the fundamental limitation on when a sparse representation is unique. Moreover, the relation between the solutions of /spl lscr//sub 0/-norm minimization and the solutions of /spl lscr//sub 1/-norm minimization indicates a computationally efficient approach to find a sparse representation. Interestingly, simulations show that the predictions made by these theorems tend to be conservative.

A multiscale coder for curves and boundaries is presented. It utilizes a multiscale structure--beamlets--that is designed primarily for linear and curvilinear features. The coder is composed of three main components: 1) a rate-distortion optimized beamlet-based representation, 2) a tree-based coding from a beamlet representation to a symbol stream, and 3) an entropy coder. This coder is named "JBEAM." Taking advantage of its multiscale property, we utilized tree-based coding to make it progressive. The derived coder has a low order of computational complexity. Simulations demonstrate an advantage over the state-of-the-art industrial standard: JBIG 2. A software package, which includes an implementation of JBEAM, is made available. Variations and potential improvements of this method will be discussed. This work may inspire more activities in this line of research, improving curve coding.

We construct detectors for "geometric" objects in noisy data. Examples include a detector for presence of a line segment of unknown length, position, and orientation in two-dimensional image data with additive white Gaussian noise. We focus on the following two issues. i) The optimal detection threshold-i.e., the signal strength below which no method of detection can be successful for large dataset size n. ii) The optimal computational complexity of a near-optimal detector, i.e., the complexity required to detect signals slightly exceeding the detection threshold. We describe a general approach to such problems which covers several classes of geometrically defined signals; for example, with one-dimensional data, signals having elevated mean on an interval, and, in d-dimensional data, signals with elevated mean on a rectangle, a ball, or an ellipsoid. In all these problems, we show that a naive or straightforward approach leads to detector thresholds and algorithms which are asymptotically far away from optimal. At the same time, a multiscale geometric analysis of these classes of objects allows us to derive asymptotically optimal detection thresholds and fast algorithms for near-optimal detectors.

Beamlets are combined with zero-tree coding algorithm to create a new coding method, particularly suitable for lines and curves. Beamlets are a multiscale collection of line segments at a range of scales, location, having a variety of lengths and orientations. The new coding scheme - named JBEAM is more efficient - in terms of bit rates - in coding binary curvy images in simulations.

Detection of inhomogeneous regions in a homogeneous background (e.g. textures) is considered. The underlying assumption is that samples from the homogeneous background reside on an underlying manifold, while samples that intersect with the embedded object (i.e. the inhomogeneous region) are 'away' from this manifold. The empirical distance from each sample (which is specified in the paper) to the manifold is a quantity used to determine the likelihood of a sample's overlapping with an embedded object. This result can consequently be integrated with the 'significant runs algorithms', to predict the presence of embedded structures. A 'local projection' algorithm is designed to estimate the distances between samples and the manifold. Simulation results for features embedded in textural imageries show promise. This work can be extended to a formal theoretical framework for underlying feature detection. It is particularly suitable for textural images.

The Fukunaga-Koontz transform (FKT) has been proposed as a feature selection methodology for nearly 32 years. There are a huge number of citations. We have not seen a direct analysis between FKT, and a well established statistical method: Fisher quadratic discriminant analysis (QDA). In this letter, under certain assumptions, we establish such a connection. We speculate that a link in a more general situation is hard to find.

A quad-tree-based hierarchical contour representation and coding method is studied. This method is based on multi scale line segments—beamlets. Simulations are reported to evaluate the effectiveness of such an approach. This is a proof-of-concept study. The reported compression ratios are not the “best”. However, the idea of tree-based coding is novel; and this idea has good potential to realize a progressive contour coding, which is important in applications such as content-based video transmission.

We consider the problem of recovering a binary image consisting of many filaments or linear fragments in the presence of severe binary noise. Our approach exploits beamlets—a dyadically organized, multiscale system of line segments—and associated fast algorithms for beamlet analysis. It considers models based on beamlet-decorated recursive dyadic partitions, and models the image as a Bernoulli random process with spatially variant success probability, which is “high” within the beamlet complexity-penalized model fitting. Simulation results demonstrate the effectiveness of the method.

Suppose a discrete-time signal S(t), 0/spl les/t<N, is a superposition of atoms taken from a combined time-frequency dictionary made of spike sequences 1/sub {t=/spl tau/}/ and sinusoids exp{2/spl pi/iwt/N}//spl radic/N. Can one recover, from knowledge of S alone, the precise collection of atoms going to make up S? Because every discrete-time signal can be represented as a superposition of spikes alone, or as a superposition of sinusoids alone, there is no unique way of writing S as a sum of spikes and sinusoids in general. We prove that if S is representable as a highly sparse superposition of atoms from this time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l/sup 1/ norm of the coefficients among all decompositions. Here "highly sparse" means that N/sub t/+N/sub w/

Automatic modulation classification (or recognition) is an intrinsically interesting problem with a variety of regulatory and military applications. We developed a method which is simple, fast, efficient and robust. The feature being used is the counts of signals falling into different parts of the signal plane. Compared with the likelihood method and the high order correlation method, it is much easier to be implemented, and the execution is much faster. When the channel model is correct, our method is efficient, in the sense that it will achieve the "optimal" classification rate. When unknown contamination is present, our method can automatically overcome it to certain degree. At SNRs of 10 and 15 dB, examples of classifying two modulation types-QAM4 and PSK6-are given. Simulations demonstrate its ability to deal with unknown noise.

We studied the stochastic behavior of inter-drop time in an M frame buffer scheme. The problem arises from digital television signal decoding. We can set up a random walk model with lower bound. The drop occurs when the random walk exceeds a pre-determined upper bound. Our main result is that, under certain conditions, the tail distribution of the inter-drop time is nearly geometric. Based on this, a numerical approximation of two important quantities-the mean of the inter-drop time and the mean of drop frequency-is developed. Simulation results verify our conclusion.