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.
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.
43263915
Image subband coding using context-based classification and adaptive quantization
Adaptive compression methods have been a key component of many proposed subband (or wavelet) image coding techniques. This paper deals with a particular type of adaptive subband image coding where we focus on the image coder's ability to adjust itself "on the fly" to the spatially varying statistical nature of image contents. This backward adaptation is distinguished from more frequently used forward adaptation in that forward adaptation selects the best operating parameters from a predesigned set and thus uses considerable amount of side information in order for the encoder and the decoder to operate with the same parameters. Specifically, we present backward adaptive quantization using a new context-based classification technique which classifies each subband coefficient based on the surrounding quantized coefficients. We couple this classification with online parametric adaptation of the quantizer applied to each class. A simple uniform threshold quantizer is employed as the baseline quantizer for which adaptation is achieved. Our subband image coder based on the proposed adaptive classification quantization idea exhibits excellent rate-distortion performance, in particular at very low rates. For popular test images, it is comparable or superior to most of the state-of-the-art coders in the literature.
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.
1444182
Detecting deception in reputation management
We previously developed a social mechanism for distributed reputation management, in which an agent combines testimonies from several witnesses to determine its ratings of another agent. However, that approach does not fully protect against spurious ratings generated by malicious agents. This paper focuses on the problem of deception in testimony propagation and aggregation. We introduce some models of deception and study how to efficiently detect deceptive agents following those models. Our approach involves a novel application of the well-known weighted majority technique to belief function and their aggregation. We describe simulation experiments to study the number of apparently accurate witnesses found in different settings, the number of witnesses on prediction accuracy, and the evolution of trust networks.
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.
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.
17844386
A retrieval technique for high-dimensional data and partially specified queries
While the persistent data of many advanced database applications, such as OLAP and scientific studies, are characterized by very high dimensionality, typical queries posed on these data appeal to a small number of relevant dimensions. Unfortunately, the multi-dimensional access methods designed for high-dimensional data perform rather poorly for these partially specified queries. The retrieval technique proposed in this paper uses a combination of two complementary measures to support efficient processing of partial queries over high-dimensional data. First, an elaborate storage organization, called the inverted space, allows the system administrator to control the size of individual indexes in order to avoid the negative impact of extremely high data dimensionality on the retrieval performance. Second, a new indexing structure, which is designed to support the inverted-space storage organization, enables efficient query processing in projected spaces with moderate dimensionality. This indexing mechanism is a general-purpose point access method that effectively attacks the limitations of KDB-trees in spaces with many dimensions, while preserving the simplicity and relatively good performance of the later structure in low-dimensional spaces. The analytical and experimental results show that the new indexing scheme outperforms two other variants of KDB-trees investigated in the paper for both fully and partially specified queries.
1366256
Convexity of Minimal Total Dominating Functions in Graphs
A total dominating function (TDF) of a graph G=(V, E) is a function f ∶ V → [0,1] such that for each v ∈ V, the sum of f values over all neighbours of ν (i.e., all vertices adjacent to v) is at least one. Integer-valued TDFs are precisely the characteristic functions of total dominating sets of G. A minimal TDF (MTDF) is one such that decreasing any value of it makes it non-TDF. An MTDF f is called universal if convex combinations of f and any other MTDF are minimal. We give a sufficient condition for an MTDF to be universal which generalizes previous results. Also we define a splitting operation on a graph G as follows: take any vertex ν in G and a vertex ω not in G and join ω with all the neighbours of v. A graph G has a universal MTDF if and only if the graph obtained by splitting G has a universal MTDF. A corollary is that graphs obtained by the operation from paths, cycles, complete graphs, wheels, and caterpillar graphs have a universal MTDF.