Search

Constrained regression problems appear in the context of optimal nonlinear filtering, as well as in a variety of other contexts, e.g., chromatographic analysis in chemometrics and manufacturing, and spectral estimation. This paper presents novel mathematical programming algorithms for some important constrained regression problems in IRN . For brevity, we focus on four key problems, namely, locally monotonic regression (the optimal counterpart of iterated median filtering), and the related problem of piecewise monotonic regression, runlength-constrained regression (a useful segmentation and edge detection technique), and uni- and oligo- modal regression (of interest in chromatography and spectral estimation). The proposed algorithms are exact and efficient, and they also naturally suggest slightly suboptimal but very fast approximate algorithms, which may be preferable in practice.

Building on earlier work, we pose the following optimization: Given a sequence of finite extent, find a finite-alphabet sequence of finite extent, which satisfies a hard structural (syntactic) constraint (e.g., it is piecewise constant of plateau run-length > M, or locally monotonic of a given lomo-degree), and which minimizes the sum of a per-letter fidelity measure, and a first-order smoothness-complexity measure. This optimization represents the unification and outgrowth of several digital nonlinear filtering schemes, including the digital counterpart of the so-called Weak Continuity (WC) formulation of Mumford-Shah and Blake-Zisserman, the Minimum Description Length (MDL) approach of Leclerc, and previous work by the first author in so- called VORCA filtering and Digital Locally Monotonic Regression. It is shown that the proposed optimization admits efficient Viterbi-type solution, and overcomes a shortcoming of WC, while preserving its unique strengths. Similarly, it overcomes a drawback of VORCA and Digital Locally Monotonic Regression, while maintaining robustness to outliers.

In [1], Restrepo and Bovik developed an elegant mathematical framework in which they studied locally monotonic regressions in RN . The drawback is that the complexity of their algorithms is exponential in N. In this paper, we consider digital locally monotonic regressions, in which the output symbols are drawn from a finite alphabet, and, by making a connection to Viterbi decoding, provide a fast O(|A|2 aN) algorithm that computes any such regression, where |A| is the size of the digital output alphabet, a stands for lomo-degree, and N is sample size. This is linear in N , and it renders the technique applicable in practice.

In two recent papers [1], [2], Sidiropoulos et al. have obtained statistical proofs of Maximum A Posteriori} (MAP) optimality and strong consistency of certain popular classes of Morphological filters, namely, Morphological Openings, Closings, unions of Openings, and intersections of Closings, under i.i.d. (both pixel-wise, and sequence-wide) assumptions on the noise model. In this paper we revisit this classic filtering problem, and prove MAP optimality and strong consistency under a different, and, in a sense, more appealing set of assumptions, which allows the explicit incorporation of geometric and Morphological constraints into the noise model, i.e., the noise may now exhibit structure; Surprisingly, it turns out that this affects neither the optimality nor the consistency of these field-proven filters.

We model digital binary image data as realizations of a bounded discrete random set, a mathematical object which can be directly defined on a finite lattice. We consider the problem of estimating realizations of discrete random sets distorted by a degradation process which can be described by a union/intersection model. First we present an important structural result concerning the probabilistic specification of discrete random sets defined on a finite lattice. Then we formulate the optimal filtering problem for the case of discrete random sets. Two distinct filtering approaches are pursued. For images which feature strong spatial statistical variations we propose a simple family of spatially varying filters, which we call mask filters, and, for each degradation model, derive explicit formulas for the optimal Mask filter. We also consider adaptive mask filters, which can be effective in a more general setting. For images which exhibit a stationary behavior, we consider the class of Morphological filters. First we provide some theoretical justification for the popularity of certain Morphological filtering schemes. In particular, we show that if the signal is smooth, then these schemes are optimal (in the sense of providing the MAP estimate of the signal) under a reasonable worst-case statistical scenario. 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 which do not rely on strong assumptions regarding the spatial interaction of geometrical primitives of the signal and the noise. This approach corresponds to a somewhat counter- intuitive use of fundamental morphological operators; however it is exactly this mode of the use that enables us to arrive at characterizations of optimality in terms of the fundamental functionals of random set theory, namely the generating functionals of the signal and the noise.

The objective of this dissertation is the systematic study of several aspects of modeling, statistical inference, and filtering of "random" binary digital images, or, uniformly bounded discrete random sets. This study consists of two interleaved parts. In the first part, we consider some important aspects of a theory of uniformly bounded discrete random sets. The fundamental result is a strengthened version of a backbone theorem of continuous- domain random set theory, namely the uniqueness theorem of Choquet-Kendall-Matheron, for the case of uniformly bounded discrete random 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 uniforml

We consider the two dimensional Analytic Bezout Equation (ABE) and investigate the properties of a particular solution, based on certain conditions imposed on the convolution kernels. We use a family of suitably chosen sensors which besides being strongly coprime also satisfies additional technical conditions. The results permit the reconstruction of the original signal with arbitrarily good resolution, i.e. achieving arbitrarily large bandwidths, depending solely upon computational resources. The theoretical foundations of this technique provide a rigorous mathematical framework, and simulation results have been promising. The feasibility of construction reasonable good discrete-time, finite-bandwidth approximations has been established, and efficient Data Parallel Grid layouts that perform the required computation have been designed. A number of implementation problems arising out of the need to approximate a basically infinite computation have been addressed.

Recent literature on robust statistical inference suggests that promising outlier rejection schemes can be based on accounting explicitly for sparse gross errors in the modeling, and then relying on compressed sensing ideas to perform the outlier detection. In this paper, we consider two models for recovering a sparse signal from noisy measurements, possibly also contaminated with outliers. The models considered here are a linear regression model, and its natural one-bit counterpart where measurements are additionally quantized to a single bit. Our contributions can be summarized as follows: We start by providing conditions for identification and the Cramér-Rao Lower Bounds (CRLBs) for these two models. Then, focusing on the one-bit model, we derive conditions for consistency of the associated Maximum Likelihood estimator, and show the performance of relevant ℓ1-based relaxation strategies by comparing against the theoretical CRLB.

Conjoint analysis (CA) is a classical tool used in preference assessment, where the objective is to estimate the utility function of an individual, or a group of individuals, based on expressed preference data. An example is choice-based CA for consumer profiling, i.e., unveiling consumer utility functions based solely on choices between products. A statistical model for choice-based CA is investigated in this paper. Unlike recent classification-based approaches, a sparsity-aware Gaussian maximum likelihood (ML) formulation is proposed to estimate the model parameters. Drawing from related robust parsimonious modeling approaches, the model uses sparsity constraints to account for outliers and to detect the salient features that influence decisions. Contributions include conditions for statistical identifiability, derivation of the pertinent Cramér-Rao Lower Bound (CRLB), and ML consistency conditions for the proposed sparse nonlinear model. The proposed ML approach lends itself naturally to ℓ1-type convex relaxations which are well-suited for distributed implementation, based on the alternating direction method of multipliers (ADMM). A particular decomposition is advocated which bypasses the apparent need for outlier communication, thus maintaining scalability. The performance of the proposed ML approach is demonstrated by comparing against the associated CRLB and prior state-of-the-art using both synthetic and real data sets.