1825087
The Minimum Description Length Principle in Coding and Modeling
We review the principles of minimum description length and stochastic complexity as used in data compression and statistical modeling. Stochastic complexity is formulated as the solution to optimum universal coding problems extending Shannon's basic source coding theorem. The normalized maximized likelihood, mixture, and predictive codings are each shown to achieve the stochastic complexity to within asymptotically vanishing terms. We assess the performance of the minimum description length criterion both from the vantage point of quality of data compression and accuracy of statistical inference. Context tree modeling, density estimation, and model selection in Gaussian linear regression serve as examples.
1767373
Wavelet thresholding via MDL for natural images
We study the application of Rissanen's (1989) principle of minimum description length (MDL) to the problem of wavelet denoising and compression for natural images. After making a connection between thresholding and model selection, we derive an MDL criterion based on a Laplacian model for noiseless wavelet coefficients. We find that this approach leads to an adaptive thresholding rule. While achieving mean-squared-error performance comparable with other popular thresholding schemes, the MDL procedure tends to keep far fewer coefficients. From this property, we demonstrate that our method is an excellent tool for simultaneous denoising and compression. We make this claim precise by analyzing MDL thresholding in two optimality frameworks; one in which we measure rate and distortion based on quantized coefficients and one in which we do not quantize, but instead record rate simply as the number of nonzero coefficients.
15189341
Wavelet thresholding for multiple noisy image copies
This correspondence addresses the recovery of an image from its multiple noisy copies. The standard method is to compute the weighted average of these copies. Since the wavelet thresholding technique has been shown to effectively denoise a single noisy copy, we consider in this paper combining the two operations of averaging and thresholding. Because thresholding is a nonlinear technique, averaging then thresholding or thresholding then averaging produce different estimators. By modeling the signal wavelet coefficients as Laplacian distributed and the noise as Gaussian, our investigation finds the optimal ordering to depend on the number of available copies and on the signal-to-noise ratio. We then propose thresholds that are nearly optimal under the assumed model for each ordering. With the optimal and near-optimal thresholds, the two methods yield similar performance, and both show considerable improvement over merely averaging.
39243731
A rate of convergence result for a universal D-semifaithful code
The problem of optimal rate universal coding is considered in the context of rate-distortion theory. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to approach its lower bound, the rate-distortion function, at a rate O(n/sup -1/log n), and this is conjectured to be optimal based on a result of A.J. Pilc (1968). Issues of constructiveness and universality are addressed. >
2174351
On Model Selection Consistency of Lasso
Sparsity or parsimony of statistical models is crucial for their proper interpretations, as in sciences and social sciences. Model selection is a commonly used method to find such models, but usually involves a computationally heavy combinatorial search. Lasso (Tibshirani, 1996) is now being used as a computationally feasible alternative to model selection. Therefore it is important to study Lasso for model selection purposes. 
 
In this paper, we prove that a single condition, which we call the Irrepresentable Condition, is almost necessary and sufficient for Lasso to select the true model both in the classical fixed p setting and in the large p setting as the sample size n gets large. Based on these results, sufficient conditions that are verifiable in practice are given to relate to previous works and help applications of Lasso for feature selection and sparse representation. 
 
This Irrepresentable Condition, which depends mainly on the covariance of the predictor variables, states that Lasso selects the true model consistently if and (almost) only if the predictors that are not in the true model are "irrepresentable" (in a sense to be clarified) by predictors that are in the true model. Furthermore, simulations are carried out to provide insights and understanding of this result.
12479973
Adaptive wavelet thresholding for image denoising and compression
The first part of this paper proposes an adaptive, data-driven threshold for image denoising via wavelet soft-thresholding. The threshold is derived in a Bayesian framework, and the prior used on the wavelet coefficients is the generalized Gaussian distribution (GGD) widely used in image processing applications. The proposed threshold is simple and closed-form, and it is adaptive to each subband because it depends on data-driven estimates of the parameters. Experimental results show that the proposed method, called BayesShrink, is typically within 5% of the MSE of the best soft-thresholding benchmark with the image assumed known. It also outperforms SureShrink (Donoho and Johnstone 1994, 1995; Donoho 1995) most of the time. The second part of the paper attempts to further validate claims that lossy compression can be used for denoising. The BayesShrink threshold can aid in the parameter selection of a coder designed with the intention of denoising, and thus achieving simultaneous denoising and compression. Specifically, the zero-zone in the quantization step of compression is analogous to the threshold value in the thresholding function. The remaining coder design parameters are chosen based on a criterion derived from Rissanen's minimum description length (MDL) principle. Experiments show that this compression method does indeed remove noise significantly, especially for large noise power. However, it introduces quantization noise and should be used only if bitrate were an additional concern to denoising.
41617522
Validation-based reprocessing scheme for updating spatial data in mobile computing environments
This paper introduces a novel reprocessing-transaction model that handles the update conflicts between mobile transactions without abortion. The proposed model executes a new subtransaction, called a reprocessing transaction, which reupdates only conflicted objects using foreign conflicted objects. We also propose a progressive reprocessing scheme to allow the non-conflicted objects of a mobile transaction to be incrementally exposed to other concurrent transactions in order to alleviate starvation of reprocessing transactions.
15548673
Adaptive Query Processing in Point-Transformation Schemes
Point-transformation schemes transform multidimensional points to one-dimensional values so that conventional access methods can be used to index multidimensional points, enabling convenient integration of multidimensional query facilities into complex transactional database management systems. However, in high-dimensional data spaces, the computational complexity of the required query transformation is prohibitive. This paper proposes a near-optimal solution based on our novel ideas of adaptive Z-ordering. The experimental results show that the proposed approach significantly improves the query performance of point-transformation schemes. The idea can easily be generalized to accommodate any hierarchical space-filling curve, not just the Z-curve.
10366637
Inverted-space storage organization for persistent data of very high dimensionality
Contemporary database technology is severely limited in managing the high-dimensional data of many advanced applications, such as multimedia systems and data mining. The main concern of this paper is the well-known performance degradation of multi-dimensional access methods in spaces with many dimensions. The paper proposes an elaborate storage organization, called the inverted space, which can support efficient processing of data in spaces with very high dimensionality. The organization allows system administrators to control the size of spatial indexes and thereby to avoid the negative impact of extremely high data dimensionality on the retrieval performance. In addition, this paper introduces a new point access method designed to address numerous other problems that contemporary retrieval schemes experience in high-dimensional situations. This mechanism is envisioned to serve as the core indexing structure of inverted-space storage organizations.
12078838
Scalable and reliable data delivery in mobile ad hoc sensor networks
This paper studies scalable data delivery algorithms in mobile ad hoc sensor networks with node and link failures. Many algorithms have been developed for data delivery and fusion in static microsensor networks, but most of them are not appropriate for mobile sensor networks due to their heavy traffic and long latency. In this paper we propose an efficient and robust data delivery algorithm for distributed data fusion in mobile ad hoc sensor networks, where each node controls its data flows and learns routing decisions solely based on their local knowledge. We analyze the localized algorithm in a formal model and validate our model using simulations. The experiments indicate that controlled data delivery processes significantly increase the probability of relevant data being fused in the network even with limited local knowledge of each node and relatively small hops of data delivery.
9205595
A spatiotemporal uncertainty model of degree 1.5 for continuously changing data objects
To support emerging database applications that deal with continuously changing (or moving) data objects (CCDO), one requires an efficient data management system that can store, update, and retrieve large sets of CCDOs. Although actual CCDOs can continuously change, computer systems cannot deal with continuously occurring infinitesimal changes. Thus, in the data management system, each object's spatiotemporal values are always associated with a certain degree of uncertainty at every point in time, and the queries are mostly processed over estimates characterizing the uncertainty. Unfortunately, there is a marked lack of formal explication of the uncertainty of multidimensional CCDOs in space-time. This paper presents our logical and mathematical bases for capturing, representing, and processing CCDOs of varying dimensionality.