The Secretary problem is a classical sequential decision-making question that can be succinctly described as follows: a set of rank-ordered applicants are interviewed sequentially for a single position. Once an applicant is interviewed, an immediate and irrevocable decision is made if the person is to be offered the job or not and only applicants observed so far can be used in the decision process. The problem of interest is to identify the stopping rule that maximizes the probability of hiring the highest-ranked applicant. A multiple-choice version of the Secretary problem, known as the Dowry problem, assumes that one is given a fixed integer budget for the total number of selections allowed to choose the best applicant. It has been solved using tools from dynamic programming and optimal stopping theory. We provide the first combinatorial proof for a related new query-based model for which we are allowed to solicit the response of an expert to determine if an applicant is optimal. Since the selection criteria differ from those of the Dowry problem, we obtain nonidentical expected stopping times.

We study the parametric online changepoint detection problem, where the underlying distribution of the streaming data changes from a known distribution to an alternative that is of a known parametric form but with unknown parameters. We propose a joint detection/estimation scheme, which we call Window-Limited CUSUM, that combines the cumulative sum (CUSUM) test with a sliding window-based consistent estimate of the post-change parameters. We characterize the optimal choice of the window size and show that the Window-Limited CUSUM enjoys first-order asymptotic optimality as average run length approaches infinity under the optimal choice of window length. Compared to existing schemes with similar asymptotic optimality properties, our test can be much faster computed because it can recursively update the CUSUM statistic by employing the estimate of the post-change parameters. A parallel variant is also proposed that facilitates the practical implementation of the test. Numerical simulations corroborate our theoretical findings.

Optimum parameter estimation methods require knowledge of a parametric probability density that statistically describes the available observations. In this work we examine Bayesian and non-Bayesian parameter estimation problems un-der a data-driven formulation where the necessary parametric probability density is replaced by available data. We present various data-driven versions that either result in neural network approximations of the optimum estimators or in well defined optimization problems that can be solved numerically. In particular, for the data-driven equivalent of non-Bayesian estimation we end up with optimization problems similar to the ones encountered for the design of generative networks.

Generative models can be used, as an alternative to conventional probability densities, to capture the statistical behavior of complicated datasets. Unlike probability densities with which the generation of realizations may become a challenging task, generative models have an inherent ability to easily produce realizations, which, in the case of natural images can be extremely realistic. In many image restoration problems, such as deblurring, colorization, inpainting, super-resolution, etc., probability densities are used as priors, one may therefore wonder whether we can, instead, adopt generative models. Indeed such methods have appeared in the literature, but they require exact knowledge of the transformations responsible for the data distortion and involve regularizer terms with weights that require adjustment. Our approach, by combining maximum a-posteriori probability with maximum likelihood estimation, can successfully restore images in both blind and non-blind modes without the need to fine-tune any regularization parameters. Simulations on deblurring, colorization, and image separation problems with exact knowledge of the transformation demonstrate improved image quality, reduced computational cost compared to existing methods. Comparable results are also enjoyed when the distortion models contain unknown parameters.

We are interested in the design of generative networks. The training of these mathematical structures is mostly performed with the help of adversarial (min-max) optimization problems. We propose a simple methodology for constructing such problems assuring, at the same time, consistency of the corresponding solution. We give characteristic examples developed by our method, some of which can be recognized from other applications, and some are introduced here for the first time. We present a new metric, the likelihood ratio, that can be employed online to examine the convergence and stability during the training of different Generative Adversarial Networks (GANs). Finally, we compare various possibilities by applying them to well-known datasets using neural networks of different configurations and sizes.

In multi-stream sequential change-point detection it is assumed that there are$M$processes in a system and at some unknown time, an occurring event changes the distribution of the samples of a particular process. In this article, we consider this problem under a sampling control constraint when one is allowed, at each point in time, to sample a single process. The objective is to raise an alarm as quickly as possible subject to a proper false alarm constraint. We show that under sampling control, a simple myopic-sampling-based sequential change-point detection strategy is second-order asymptotically optimal when the number$M$of processes is fixed. This means that the proposed detector, even by sampling with a rate$1/M$of the full rate, enjoys the same detection delay, up to some additive finite constant, as the optimal procedure. Simulation experiments corroborate our theoretical results.

The problem studied is one of quickest detection of an anomaly that emerges in a sensor network, and which may move across the network after it emerges. Each sensor in the network is characterized by a non-anomalous and an anomalous data-generating distribution, and these distributions could be different across the sensors. Initially, the observations at all the sensors are generated according to their corresponding non-anomalous distribution. After some unknown but deterministic time instant, a dynamic anomaly emerges in the network, affecting a different sensor as time progresses. The observations generated by the affected sensor follow the corresponding anomalous distribution. The goal is to detect the onset of the dynamic anomaly as quickly as possible, subject to constraints on the frequency of false alarms. This detection problem is posed in a quickest change detection framework where candidate stopping procedures are evaluated according to a delay metric that considers the worst trajectory of the dynamic anomaly. A detection rule is proposed and established to be asymptotically optimal as the mean time to false alarm goes to infinity. Finally, numerical results are provided to validate our theoretical analysis.

In the sequential change-point detection problem for multi-stream data, it is assumed that there are M processes in a system and at some unknown time, an occurring event impacts one unknown local process in the sense of changing the distribution of observations from that affected local process. In this paper, we consider such problem under the sampling control constraint, in which one is able to take observations from only one of the local processes at each time step. Our objective is to design an adaptive sampling policy and a stopping time policy that is able to raise a correct alarm as quickly as possible subject to the false alarm and sampling control constraint. We develop an efficient sequential change-point detection algorithm under the sampling control that turns out to be second-order asymptotically optimal under the full data scenario. That is, with the sampling rate that is only 1/M of the full data scenario, our proposed algorithm has the same performance up to second-order as the optimal procedure under the full data scenario.

We consider the problem of sequential detection of a change in the statistical behavior of a hidden Markov model. By adopting a worst-case analysis with respect to the time of change and by taking into account the data that can be accessed by the change-imposing mechanism we offer alternative formulations of the problem. For each formulation we derive the optimum Shewhart test that maximizes the worst-case detection probability while guaranteeing infrequent false alarms.

We consider the sequential change-point detection for asynchronous multi-sensors, where each sensor observe a signal (due to change-point) at different times. We propose an asynchronous Subspace-CUSUM procedure based on jointly estimating the unknown signal waveform and the unknown relative delays between sensors. Using the estimated delays, we can align signals and use the subspace to combine multiple sensor observations. We derive the optimal drift parameter for the proposed procedure, and characterize the relationship between the expected detection delay, average run length (of false alarms), and the energy of the time-varying signal. We demonstrate the good performance of the proposed procedure using simulation and real data. We also demonstrate that the proposed procedure outperforms the well-known "one-shot procedure" in detecting weak and asynchronous signals.

We propose an optimal sequential methodology for obtaining confidence intervals for a binomial proportion θ. Assuming that an independent and identically distributed sequence of Bernoulli (θ) trials is observed sequentially, we are interested in designing: 1) a stopping time T that will decide the best time to stop sampling the process and 2) an optimum estimator θ̂T that will provide the optimum center of the interval estimate of θ. We follow a semi-Bayesian approach, where we assume that there exists a prior distribution for θ, and our goal is to minimize the average number of samples while we guarantee a minimal specified coverage probability level. The solution is obtained by applying standard optimal stopping theory and computing the optimum pair (T, θ̂T) numerically. Regarding the optimum stopping time component T, we demonstrate that it enjoys certain very interesting characteristics not commonly encountered in solutions of other classical optimal stopping problems. In particular, we prove that, for a particular prior (beta density), the optimum stopping time is always bounded from above and below; it needs to first accumulate a sufficient amount of information before deciding whether or not to stop, and it will always terminate before some finite deterministic time. We also conjecture that these properties are present with any prior. Finally, we compare our method with the optimum fixed-sample-size procedure as well as with existing alternative sequential schemes.

In multichannel sequential change detection, multiple sensors monitor a system in which an abrupt change occurs at some unknown time and is perceived by an unknown subset of sensors. The goal is to detect this change quickly, while controlling the rate of false alarms. In the traditional asymptotic analysis of this problem, the false alarm rate goes to 0 while all other parameters remain fixed. We argue that this framework is not very informative, as the corresponding asymptotic optimality property cannot differentiate between universal and parsimonious rules. We propose an asymptotic framework in which the number of sensors also goes to infinity, and we show that in this context universal rules may fail to be asymptotically optimal when the number of streams is not very small. On the other hand, parsimonious rules are shown to be asymptotically optimal under reasonable sparsity conditions.

We study the problem of testing between a sparse signal in noise, modeled as a mixture distribution, versus pure noise, with a Gaussian signal and noise of same variance, but differing means as the mixture proportion tends to zero. We construct a simple new adaptive test based on quantizing data with sample size-dependent quantizers and prove its consistency. The proposed test has almost linear time complexity and sublinear space complexity, which is better than existing tests, and in particular, the celebrated Higher Criticism test. Moreover, our numerical results show that the proposed test is competitive with commonly used tests even with a small number of quantizer levels.

We consider the problem of parameter estimation under a sequential framework. Specifically we assume that an i.i.d. random process is observed sequentially with its common pdf having a random parameter that must be estimated. We are interested in designing a stopping time that will decide when is the best moment to stop sampling the process and an estimator that will use the acquired samples in order to provide the desired estimate. We follow a semi-Bayesian approach where we assign cost to the pair (estimate, true parameter) and our goal is to minimize the average sample size guaranteeing at the same time an average cost below some prescribed level. For our analysis we adopt a conditional average cost which leads to a considerable simplification in the sequential estimation problem, otherwise known to be analytically intractable. We apply our results to a number of examples and compare our method with the optimum fixed sample size but also with existing sequential schemes.

In this paper, we study the rate of decay of the probability of error for distinguishing between a sparse signal with noise, modeled as a sparse mixture, from pure noise. This problem has many applications in signal processing, evolutionary biology, bioinformatics, astrophysics and feature selection for machine learning. We let the mixture probability tend to zero as the number of observations tends to infinity and derive oracle rates at which the error probability can be driven to zero for a general class of signal and noise distributions. In contrast to the problem of detection of non-sparse signals, we see the log-probability of error decays sublinearly rather than linearly and is characterized through the x2-divergence rather than the Kullback-Leibler divergence. This work provides the first characterization of the rate of decay of the error probability for this problem.

We are interested in the sequential detection of a change in the statistical behavior of a random process. Specifically we consider changes that are not abrupt but exhibit a transitory phase before reaching their steady-state behavior. Adopting the classical worst-case conditional detection delay proposed by Lorden as our performance measure and constraining the average false-alarm period, we derive the sequential test that optimizes, in the exact sense, the proposed criterion. The resulting optimum rule resembles the well known CUSUM rule with the corresponding test-statistic-update being not only a function of all pre- and post-change pdfs but also of the false-alarm constraint.

Opportunistic detection rules (ODRs) are variants of fixed-sample-size detection rules in which the statistician is allowed to make an early decision on the alternative hypothesis opportunistically based on the sequentially observed samples. From a sequential decision perspective, ODRs are also mixtures of one-sided and truncated sequential detection rules. Several results regarding ODRs are established in this paper. In the finite regime, the maximum sample size is modeled either as a fixed finite number, or a geometric random variable with a fixed finite mean. For both cases, the corresponding Bayesian formulations are investigated. The former case is a slight variation of the well-known finite-length sequential hypothesis testing procedure in the literature, whereas the latter case is new, for which the Bayesian optimal ODR is shown to be a sequence of likelihood ratio threshold tests with two different thresholds. A running threshold, which is determined by solving a stationary state equation, is used when future samples are still available, and a terminal threshold (simply the ratio between the priors scaled by costs) is used when the statistician reaches the final sample and, thus, has to make a decision immediately. In the asymptotic regime, the tradeoff among the exponents of the (false alarm and miss) error probabilities and the normalized expected stopping time under the alternative hypothesis is completely characterized and proved to be tight, via an information-theoretic argument. Within the tradeoff region, one noteworthy fact is that the performance of the Stein-Chernoff lemma is attainable by ODRs.

Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser near-optimal roadmaps, which have reduced running time and storage requirements.

Opportunistic detection rules (ODRs) are variants of fixed-sample-size detection rules in which the statistician is allowed to make an early decision on the alternative hypothesis opportunistically based on the sequentially observed samples. From a sequential decision perspective, ODRs are also mixtures of one-sided and truncated sequential detection rules. Several key properties of ODRs are established in this paper, in both the asymptotic regime in which the maximum sample size grows without bound, and the finite regime in which the maximum samples size is a fixed finite number. Furthermore, an extended setup, in which the maximum sample size is a random variable following a geometric distribution whose realization is not revealed to the statistician until observing the last sample, is studied.

We develop optimal centralized sequential estimators under different formulations of the problem. Decentralized sequential estimation is also considered for wireless sensor networks. We propose an asymptotically optimal decentralized scheme based on level-triggered sampling, a non-uniform sampling technique. Performance of the proposed scheme is analyzed.

We consider a well-defined joint detection and parameter estimation problem. By combining the Bayesian formulation of the estimation subproblem with suitable constraints on the detection subproblem, we develop optimum one- and two-step test for the joint detection/estimation setup. The proposed combined strategies have the very desirable characteristic to allow for the trade-off between detection power and estimation quality. Our theoretical developments are, then, applied to the problems of retrospective changepoint detection and multiple-input multiple-output (MIMO) radar. In the former case, we are interested in detecting a change in the statistics of a set of available data and provide an estimate for the time of change, while in the latter in detecting a target and estimating its location. Intense simulations in the MIMO radar example demonstrate that by using jointly optimum schemes, we can experience significant improvement in estimation quality, as compared to generalized the likelihood ratio test or the test that treats the two subproblems separately, with only small sacrifices in detection power.

We consider the problem of simultaneous binary hypothesis testing and parameter estimation. By defining suitable joint formulations we develop combined detection and estimation strategies that are optimum. Key point of the proposed methodologies constitutes the fact that they integrate both well known approaches, namely Bayesian and Neyman-Pearson.

An asymptotically optimum test for the problem of decentralized sequential hypothesis testing is presented. The induced communication between sensors and fusion center is asynchronous and limited to 1-bit data. When the sensors observe continuously stochastic processes with continuous paths, the proposed test is order-2 asymptotically optimal, in the sense that its inflicted performance loss is bounded. When the sensors take discrete time observations, the proposed test achieves order-1 asymptotic optimality, i.e., the ratio of its performance over the optimal performance tends to 1. Moreover, we show theoretically and corroborate with simulations that the performance of the suggested test in discrete time can be significantly improved when the sensors sample their underlying continuous time processes more frequently, a property which is not enjoyed by other centralized or decentralized tests in the literature.

The widespread deployment of wireless networks and hot spots that employ the IEEE 802.11 technology has forced network designers to put emphasis on the importance of ensuring efficient and fair use of network resources. In this work we propose a novel framework for detection of intelligent adaptive adversaries in the IEEE 802.11 MAC by addressing the problem of detection of the worst-case scenario attacks. Utilizing the nature of this protocol we employ sequential detection methods for detecting greedy behavior and illustrate their performance for detection of least favorable attacks. By using robust statistics in our problem formulation, we attempt to utilize the precision given by parametric tests, while avoiding the specification of the adversarial distribution. This approach establishes the lowest performance bound of a given Intrusion Detection System (IDS) in terms of detection delay and is applicable in online detection systems where users who pay for their services want to obtain the information about the best and the worst case scenarios and performance bounds of the system. This framework is meaningful for studying misbehavior due to the fact that it does not focus on specific adversarial strategies and therefore is applicable to a wide class of adversarial strategies.

This paper describes the analytical derivation of a new watermarking algorithm satisfying optimality properties when the distortion of the watermarked signal is caused by a Gaussian process. We also extend previous work under the same assumptions and obtain more general solutions.

Selfish behavior at the Medium Access (MAC) Layer can have devastating side effects on the performance of wireless networks, with effects similar to those of Denial of Service (DoS) attacks. In this paper we consider the problem of detection and prevention of node misbehavior at the MAC layer, focu sing on the back-off manipulation by selfish nodes. We first propose an algorithm that ensures honest behavior of non-colluding participants. Furthermore, we analyze the problem of colluding selfish nodes, casting the problem within a minimax robust detection framework and providing an optimal detection rule for the worst-case attack scenarios. Finally, we evaluate the performance of single and colluding attackers in terms of detection delay. Although our approach is general and can be used with any probabilistic distributed MAC protocol, we focus our analysis on the IEEE 802.11 MAC.

We consider the problem of decentralized change detection using the CUSUM test. More than one sensors acquire independent signals and send their quantized version to a fusion center that uses this information to detect a simultaneous change in all sensors. By introducing a recurrence relation that defines the optimum performance of the CUSUM test for given quantization, we further optimize this measure with respect to the quantization scheme. We compare the resulting optimum test with a simple, asynchronous one shot strategy, where each sensor performs a local CUSUM test and communicates with the fusion center only once to signal its detection

We consider the problem of blind channel estimation in zero padding OFDM systems, and propose blind adaptive algorithms in order to identify the impulse response of the multipath channel. In particular, we develop RLS and LMS schemes that exhibit rapid convergence combined with low computational complexity and numerical stability. Both versions are obtained by properly modifying the orthogonal iteration method used in numerical analysis for the computation of singular vectors. With a number of simulation experiments we demonstrate the satisfactory performance of our adaptive schemes under diverse signaling conditions

The problem of blind adaptive channel estimation in OFDM systems is considered. Focusing on the zero padding approach, for the first time adaptive algorithms are proposed that blindly identify the impulse response of the multipath channel. In particular, we develop RLS and LMS schemes that exhibit rapid convergence combined with low computational complexity. Both versions are obtained by properly modifying the orthogonal iteration, a method used in numerical analysis for the computation of singular vectors. With a number of simulations we demonstrate the satisfactory performance of our adaptive schemes under diverse signaling conditions.

The problem of blind adaptive channel estimation, in code-division multiple-access (CDMA) systems, is considered. Using only the spreading code of the user of interest and the received data, adaptive techniques are proposed that blindly identify the impulse response of the multipath channel. In particular, we develop RLS and LMS implementations that exhibit rapid convergence combined with low computational complexity. Both versions were inspired by the iterative power method used in numerical analysis to compute the singular vector corresponding to the largest singular value of a matrix. This is the reason why our schemes exhibit performance comparable to SVD off-line techniques while outperforming, significantly, existing adaptive methods proposed in the literature.

The problem of channel estimation in code division multiple access (CDMA) systems are considered. Using only the spreading code of the user of interest, a technique is proposed to identify the impulse response of the multipath channel from the received data sequence. While existing blind methods suffer from high computational complexity and sensitivity to accurate knowledge of the noise subspace rank, the proposed method overcomes both problems. In particular we estimate the noise subspace by a simple matrix power that is computationally efficient and requires no knowledge of the noise subspace rank. Once an estimate of the noise subspace is available the channel impulse response can be directly identified through a small size SVD or a least squares approach. Extensive simulations demonstrate similar performance of our method as compared to the existing schemes but a considerably lower computational cost.

A well-known least squares optimum approximation method is proposed as an efficient initialization scheme for the Remez exchange algorithm. More specifically, we theoretically demonstrate that the "don't care" least squares optimum solution guarantees, inside the bands of interest, the correct number of alternating in-sign extrema of the error function, thus satisfying one of the two basic conditions that are sufficient for obtaining the L/sub /spl infin// optimum solution. Although convergence of Remez: is theoretically assured, its practical implementations may fail to converge in "difficult" design problems when classical initialization is used. In particular, Matlab's realization of Remez, when initialized with the proposed scheme, exhibits a significantly better overall performance that translates into faster convergence and more robust behavior, especially in difficult design problems.

Adaptive blind source separation algorithms are conventionally composed of two parts. The first, using second order statistics, is responsible for whitening the measured signals, whereas the second, based on nonlinear statistics, imposes independence and achieves the final separation. In this work we show that this two-part scheme is in fact not necessary. By proposing a general nonlinear adaptation model, we find conditions that lead to source separation and guarantee an overall desirable symmetric behavior of the algorithm. Furthermore, using a local performance measure, we optimize the general adaptation scheme and obtain algorithms that have optimum convergence rate. Finally we show that the proposed optimum schemes, except for trivial cases, cannot be put under the two-part classical scheme of the literature, suggesting that the latter is suboptimum.

The relative error probability performance of three linear multiuser detectors-the minimum mean-square error (MMSE) detector, the decorrelator, and the conventional matched filter (MF) detector-is investigated under nonorthogonal signaling and additive white Gaussian noise conditions. It is shown that, contrary to the general belief, the MMSE detector does not uniformly outperform the other two detectors. In fact, even for the two-user case, one can find counterexamples where the matched filter is significantly better.

We consider the problem of quickest detection of abrupt changes for processes that are not necessarily independent and identically distributed (i.i.d.) before and after the change. By making a very simple observation that applies to most well-known optimum stopping times developed for this problem (in particular CUSUM and Shiryayev-Roberts (1963) stopping rule) we show that their optimality can be easily extended to more general processes than the usual i.i.d. case.

A very powerful technique for computing the LS (least squares) estimates of an FIR (finite impulse response) filter's impulse response is described. It is based on the QR factorization of the input data matrix. The method consists of two parts. First the input matrix is factorized into an orthogonal Q part and an upper triangular R part. The unknown coefficients are then obtained from a triangular linear system of equations. An algorithm for solving the above linear system, which is appropriate for adaptive processing, is proposed. This is achieved via a set of Givens rotations and a modified Faddeeva scheme.>

The robust detection of signals in additive dependent noise is considered. The solution to the finite-sample problem is obtained when the Bayes risk is used as the performance measure. For the multivariate densities involved we assume that they belong to an e-contamination model. The robust detection structure is shown to be optimum for the least-favorable density and is a censored version of the nominal likelihood ratio.

New "instrumental" tests for detecting and diagnosing changes in the poles of a signal having unknown time-varying zeros are proposed. Numerical results for nonstationary scalar signals are given. The extension of these tests to the vector case may be used for vibration monitoring.

The optimum nonlinearity is defined for detection of a weak signal when minimal knowledge of the dependency structure of the observations is available. Specifically, it is assumed that the observations form a one-dependent strictly stationary sequence of random variables and that only a finite number of moments of the marginal density and the correlation coefficient between consecutive observations are known. It is assumed that the bivariate densities involved can be represented as diagonal series, using orthonormal polynomials. Using efficacy as a performance measure, the optimum nonlinearity is required to satisfy a saddle-point condition over this class of bivariate densities.

The design of a fixed filter is considered for equalization of an imprecisely known channel. The channel frequency response is assumed to have amplitude and phase characteristics lying within specified bounds at each frequency, and a minimax filter optimizing worst case mean-squared error (MSE) performance is derived. The general result is illustrated by considering a two-path channel model with an uncertain secondary path delay characteristic.

Robust detection of a signal is considered for the case of independent and identically distributed observations. Following an asymptotic but nonlocal approach, the exponential rates of decrease of the error probabilities are considered as measure of performance. Under this measure a robust detection structure for the symmetric density case is derived. This detection structure is a generalization of an existing result for the local case and is reduced to it when the signal magnitude tends to zero.

Detection of weak signals in a special\varphi-mixing noise class is considered. The detector structure is restricted to sums of memoryless nonlinear transformations of the observations, correlated with the data sequence and compared to a fixed threshold. Using the efficacy to measure performance, the nonlinearity that has min-max performance is derived.

Minimax robust Wiener filtering is considered for the case in which the signal and noise spectral-density matrix is not completely specified. Results are obtained for spectral-density matrix classes which are defined by upper and lower bounds on the components of the matrix. These results form an extension of earlier results on robust Wiener filtering for the case of uncorrelated signals and noise.

The detection of signals in noise with possibly asymmetric probability density functions is considered. The noise density model allows a symmetric contaminated-nominal central part and an arbitrary tail behavior. For detection of known signals, the robust nonlinear-correlator (NC) detector is obtained based on detector efficacy as performance criterion. The robustM-detector structure for constant-signal detection is also explicitly obtained.