Institute for Systems Research

We formulate this task as an inverse problem, specifying a well-defined cost function that has to be optimized under constraints.

In particular, we propose the use of a Linear Regularization method, which ﲭaximizes the smoothness of the estimate. Our main theoretical contribution is a Theorem, which shows that, for smooth enough distributions, we can achieve full recovery from summary data.

Our theorem is closely related to the well known Shannon-Nyquist sampling theorem.

We describe how to apply this theory to a variety of database problems, that involve partial information, such as OLAP, data warehousing and histograms in query optimization. Our main practical contribution is that the Linear Regularization method is extremely effective, both on synthetic and on real data. Our experiments show that the proposed approach almost consistently outperforms the ﲵniformity assumption, achieving significant savings in root-mean-square error: up to 20% for stock price data, and up to 90% for smoother data sets.

We formulate this task as an inverse problem, specifying a well-defined cost function that has to be optimized under constraints.

In particular, we propose the use of a Linear Regularization method, which ﲭaximizes the smoothness of the estimate. Our main theoretical contribution is a Theorem, which shows that, for smooth enough distributions, we can achieve full recovery from summary data.

Our theorem is closely related to the well known Shannon-Nyquist sampling theorem.

We describe how to apply this theory to a variety of database problems, that involve partial information, such as OLAP, data warehousing and histograms in query optimization. Our main practical contribution is that the Linear Regularization method is extremely effective, both on synthetic and on real data. Our experiments show that the proposed approach almost consistently outperforms the ﲵniformity assumption, achieving significant savings in root-mean-square error: up to 20% for stock price data, and up to 90% for smoother data sets.

The vehicle through which much of the discussion is carried out is a "special" discrete random set model, the discrete radial Boolean random set, which is closely related to the theory of Morphological shape-size distributions. The continuous-domain Boolean random set has been successfully used in a variety of applications. A good portion of the first part of this dissertation is devoted to the statistical inference of the discrete radial Boolean random set. We consider three problems: parameter estimation, binary hypothesis testing, and classification of "random" known shapes in Boolean clutter. The tools come mainly from the area of Morphological shape analysis. The focus is on inference procedures which are both computationally efficient, and statistically sound.

In the second part, we consider the problem of estimating realizations of uniformly bounded discrete random sets, distorted by a degradation process which can be described by a union/intersection noise model. Two different optimal filtering approaches are considered. The first involves a class of filters which arises quite naturally from the set-theoretic analysis of optimal filters. We call this the class of mask filters. The second approach deals with optimal Morphological filters. First, we provide some fresh statistical insight into certain "folk theorems" of Morphological filtering. We do so by exploiting the uniformly bounded discrete random set formulation of the filtering problem. Then we show that, by using an appropriate (under a given degradation model) expansion of the optimal filter, we can obtain "universal" characterizations of optimality, in terms of the fundamental functionals of random set theory, namely the generating functionals of the signal and the noise.