Search

We consider the sequential composite binary hypothesis testing problem in which one of the hypotheses is governed by a single distribution while the other is governed by a family of distributions whose parameters belong to a known set $\Gamma $. We would like to design a test to decide which hypothesis is in effect. Under the constraints that the probabilities that the length of the test, a stopping time, exceeds $n$ are bounded by a certain threshold $\epsilon $ , we obtain certain fundamental limits on the asymptotic behavior of the sequential test as $n$ tends to infinity. Assuming that $\Gamma $ is a convex and compact set, we obtain the set of all first-order error exponents for the problem. We also prove a strong converse. Additionally, we obtain the set of second-order error exponents under the assumption that the alphabet of the observations $\mathcal {X}$ is finite. In the proof of second-order asymptotics, a main technical contribution is the derivation of a central limit-type result for a maximum of an uncountable set of log-likelihood ratios under suitable conditions. This result may be of independent interest. We also show that some important statistical models satisfy the conditions. [ABSTRACT FROM AUTHOR]

We propose an optimal sequential methodology for obtaining confidence intervals for a binomial proportion $\theta$. Assuming that an independent and identically distributed sequence of Bernoulli ($\theta$) 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 $\hat{{\theta}}_{{T}}$ that will provide the optimum center of the interval estimate of $\theta$. We follow a semi-Bayesian approach, where we assume that there exists a prior distribution for $\theta$ , 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,\hat{{\theta }}_{{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. [ABSTRACT FROM AUTHOR]

A multi-armed bandit with finitely many arms is studied when each arm is a homogeneous Markov process on an underlying finite state space. The transition law of one of the arms, referred to as the odd arm, is different from the common transition law of all other arms. A learner, who has no knowledge of the above transition laws, has to devise a sequential test to identify the index of the odd arm as quickly as possible, subject to an upper bound on the probability of error. For this problem, we derive an asymptotic lower bound on the expected stopping time of any sequential test of the learner, where the asymptotics is as the probability of error vanishes. Furthermore, we propose a sequential test, and show that the asymptotic behaviour of its expected stopping time comes arbitrarily close to that of the lower bound. Prior works deal with independent and identically distributed arms, whereas our work deals with Markov arms. Our analysis of the rested Markov setting is a key first step in understanding the difficult case of restless Markov setting, which is still open. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider the problem of detecting an odd process among a group of Poisson point processes, all having the same rate except the odd process. The actual rates of the odd and non-odd processes are unknown to the decision maker. We consider a time-slotted sequential detection scenario where, at the beginning of each slot, the decision maker can choose which process to observe during that time slot. We are interested in policies that satisfy a given constraint on the probability of false detection. We propose a variation on a sequential policy based on the generalised likelihood ratio statistic. The policy, via suitable thresholding, can be made to satisfy the given constraint on the probability of false detection. Furthermore, we show that the proposed policy is asymptotically optimal in terms of the conditional expected stopping time among all policies that satisfy the constraint on the probability of false detection. The asymptotic is as the probability of false detection is driven to zero. We apply our results to a particular visual search experiment studied recently by neuroscientists. Our model suggests a neuronal dissimilarity index for the visual search task. The neuronal dissimilarity index, when applied to visual search data from the particular experiment, correlates strongly with the behavioural data. However, the new dissimilarity index performs worse than some previously proposed neuronal dissimilarity indices. We explain why this may be attributed to some experiment conditions. [ABSTRACT FROM AUTHOR]

The problem of exactly generating a general random process (target process) by using another general random process (coin process) is studied. The performance of the interval algorithm, introduced by Han and Hoshi, is analyzed from the perspective of information spectrum approach. When either the coin process or the target process has one point spectrum, the asymptotic optimality of the interval algorithm among any random number generation algorithms is proved, which demonstrates utility of the interval algorithm beyond the ergodic process. Furthermore, the feasibility condition of exact random number generation is also elucidated. Finally, the obtained general results are illustrated by the case of generating a Markov process from another Markov process. [ABSTRACT FROM AUTHOR]

This work considers the cooperative sequential hypothesis testing problem in a distributed network with quantized communication channels. The sensors observe independent sequences of samples and in the meantime, exchange their local information in the form of quantized statistics at every sampling interval. The communication links are represented as an undirected graph. In this distributed setup, every sensor performs its own sequential test based on the local samples and the messages from the neighbour sensors. Our goal is to devise the distributed sequential test that comprises the quantization scheme, the message-exchange protocol and the test procedure such that every sensor in the network fully exploits the network diversity and achieves the (asymptotically) optimal performance in terms of the stopping time. In particular, two distributed sequential tests are proposed based on different quantization schemes and a quantized message-exchange protocol that satisfies certain conditions. The first quantization scheme uniformly quantizes the local statistic at each sensor and at every sampling interval; the second one hinges on a modified level-triggered quantization technique, and resembles the Lebesgue sampling of the running local statistic. Our analyses show that the uniform quantization based distributed sequential test yields sub-optimal performance, while the one based on level-triggered quantization achieves the order-2 asymptotically optimal performance at every sensor for any fixed quantization step-size. Furthermore, we generalize the proposed sequential tests to the cluster-based network. Numerical results are provided to corroborate our analyses and demonstrate the effectiveness of the proposed sequential tests. [ABSTRACT FROM AUTHOR]

The classical problem of quickest change detection is studied with an additional constraint on the cost of observations used in the detection process. The change point is modeled as an unknown constant, and minimax formulations are proposed for the problem. The objective in these formulations is to find a stopping time and an ON–OFF observation control policy for the observation sequence, to minimize a version of the worst possible average delay, subject to constraints on the false alarm rate and the fraction of time observations are taken before change. An algorithm called DE-CuSum is proposed and is shown to be asymptotically optimal for the proposed formulations, as the false alarm rate goes to zero. Numerical results are used to show that the DE-CuSum algorithm has good tradeoff curves and performs significantly better than the approach of fractional sampling, in which the observations are skipped using the outcome of a sequence of coin tosses, independent of the observation process. This study is guided by the insights gained from an earlier study of a Bayesian version of this problem. [ABSTRACT FROM AUTHOR]

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulas with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded. [ABSTRACT FROM PUBLISHER]

We show that the optimal decision policy for several types of Bayesian sequential detection problems has a threshold switching curve structure on the space of posterior distributions. This is established by using lattice programming and stochastic orders in a partially observed Markov decision process (POMDP) framework. A stochastic gradient algorithm is presented to estimate the optimal linear approximation to this threshold curve. We illustrate these results by first considering quickest time detection with phase-type distributed change time and a variance stopping penalty. Then it is proved that the threshold switching curve also arises in several other Bayesian decision problems such as quickest transient detection, exponential delay (risk-sensitive) penalties, stopping time problems in social learning, and multi-agent scheduling in a changing world. Using Blackwell dominance, it is shown that for dynamic decision making problems, the optimal decision policy is lower bounded by a myopic policy. Finally, it is shown how the achievable cost of the optimal decision policy varies with change time distribution by imposing a partial order on transition matrices. [ABSTRACT FROM AUTHOR]

A novel quickest detection setting is proposed, generalizing the well-known Bayesian change-point detection model. Suppose {(Xi, Yi)}i≥1 is a sequence of pairs of random variables, and that S is a stopping time with respect to {Xi}i≥1. The problem is to find a stopping time T with respect to {Yi}i≥1 that optimally tracks S, in the sense that T minimizes the expected reaction delay E(T - S)+, while keeping the false-alarm probability P(T < S) below a given threshold α ϵ [0, 1]. This problem formulation applies in several areas, such as in communication, detection, forecasting, and quality control. Our results relate to the situation where the Xi's and Yi's take values in finite alphabets and where S is bounded by some positive integer κ. By using elementary methods based on the analysis of the tree structure of stopping times, we exhibit an algorithm that computes the optimal average reaction delays for all α ϵ [0, 1], and constructs the associated optimal stopping times T. Under certain conditions on {(Xi, Yi)}i≥1 and S, the algorithm running time is polynomial in κ. [ABSTRACT FROM AUTHOR]

Motivated by real-world machine learning applications, we consider a statistical classification task in a sequential setting where test samples arrive sequentially. In addition, the generating distributions are unknown and only a set of empirically sampled sequences are available to a decision maker. The decision maker is tasked to classify a test sequence which is known to be generated according to either one of the distributions. In particular, for the binary case, the decision maker wishes to perform the classification task with minimum number of the test samples, so, at each step, she declares that either hypothesis 1 is true, hypothesis 2 is true, or she requests for an additional test sample. We propose a classifier and analyze the type-I and type-II error probabilities. We demonstrate the significant advantage of our sequential scheme compared to an existing non-sequential classifier proposed by Gutman. Finally, we extend our setup and results to the multi-class classification scenario and again demonstrate that the variable-length nature of the problem affords significant advantages as one can achieve the same set of exponents as Gutman’s fixed-length setting but without having the rejection option. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Rare events can potentially occur in many applications. When manifested as opportunities to be exploited, risks to be ameliorated, or certain features to be extracted, such events become of paramount significance. Due to their sporadic nature, the information-bearing signals associated with rare events often lie in a large set of irrelevant signals and are not easily accessible. This paper provides a statistical framework for detecting such events so that an optimal balance between detection reliability and agility, as two opposing performance measures, is established. The core component of this framework is a sampling procedure that adaptively and quickly focuses the information-gathering resources on the segments of the dataset that bear the information pertinent to the rare events. Particular focus is placed on Gaussian signals with the aim of detecting signals with rare mean and variance values. [ABSTRACT FROM AUTHOR]

With a finite number of samples drawn from one of two possible distributions sequentially revealed, an opportunistic detection rule is proposed, which possibly makes an early decision in favor of the alternative hypothesis, while always deferring the decision of the null hypothesis until collecting all the samples. Properties of this opportunistic detection rule are discussed and its key asymptotic behavior in the large sample size limit is established. Specifically, a Chernoff–Stein lemma type of characterization of the exponential decay rate of the miss probability under the Neyman–Pearson criterion is established, and consequently, a performance metric of asymptotic exponential efficiency loss is proposed and discussed, which is exactly the ratio between the Kullback–Leibler distance and the Chernoff information of the two hypotheses. Analytical results are corroborated by numerical experiments. [ABSTRACT FROM AUTHOR]

We consider how local and global decision policies interact in stopping time problems such as quickest time change detection. Individual agents make myopic local decisions via social learning, that is, each agent records a private observation of a noisy underlying state process, selfishly optimizes its local utility and then broadcasts its local decision. Given these local decisions, how can a global decision maker achieve quickest time change detection when the underlying state changes according to a phase-type distribution? This paper presents four results. First, using Blackwell dominance of measures, it is shown that the optimal cost incurred in social-learning-based quickest detection is always larger than that of classical quickest detection. Second, it is shown that in general the optimal decision policy for social-learning-based quickest detection is characterized by multiple thresholds within the space of Bayesian distributions. Third, using lattice programming and stochastic dominance, sufficient conditions are given for the optimal decision policy to consist of a single linear hyperplane, or, more generally, a threshold curve. Estimation of the optimal linear approximation to this threshold curve is formulated as a simulation-based stochastic optimization problem. Finally, this paper shows that in multiagent sensor management with quickest detection, where each agent views the world according to its prior, the optimal policy has a similar structure to social learning. [ABSTRACT FROM PUBLISHER]

A Gaussian random walk (or a Wiener process), possibly with drift, is observed in a noisy or delayed fashion. The problem considered in this paper is to estimate the first time \tau the random walk reaches a given level. Specifically, the average p-moment (p\geq 1) optimization problem \inf \eta {\BBE} \vert \eta -\tau \vert ^{p} is investigated where the infimum is taken over the set of stopping times that are defined on the observation process. When there is no drift, optimal stopping rules are characterized for both types of observations. When there is a drift, upper and lower bounds on \inf \eta {\BBE} \vert \eta -\tau \vert ^{p} are established for both types of observations. The bounds are tight in the large-level regime for noisy observations and in the large-level-large-delay regime for delayed observations. Noteworthy, for noisy observations there exists an asymptotically optimal stopping rule that is a function of a single observation. Simulation results are provided that corroborate the validity of the results for non-asymptotic settings. [ABSTRACT FROM PUBLISHER]

The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended to finite-state ergodic Markov channels. For these channels, a single-letter characterization of the reliability function is presented, under the assumption of full causal output feedback, and full causal observation of the channel state both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference (ISI). Specifically, the convex-analytic approach to Markov decision processes is adopted in order to handle problems with stopping time horizons induced by variable-length coding schemes. [ABSTRACT FROM AUTHOR]

The problem of detection and possible estimation of a signal generated by a dynamic system when a variable number of noisy measurements can be taken is here considered. Assuming a Markov evolution of the system (in particular, the pair signal-observation forms a hidden Markov model (HMM)), a sequential procedure is proposed, wherein the detection part is a sequential probability ratio test (SPRT) and the estimation part relies upon a maximum a posteriori probability (MAP) criterion, gated by the detection stage (the parameter to be estimated is the trajectory of the state evolution of the system itself). A thorough analysis of the asymptotic behavior of the test in this new scenario is given, and sufficient conditions for its asymptotic optimality are stated, i.e., for almost sure minimization of the stopping time and for (first-order) minimization of any moment of its distribution. An application to radar surveillance problems is also examined. [ABSTRACT FROM AUTHOR]

Addresses the problem of detecting changes in multivariate Gaussian random signals with an unknown mean after the change through the window-limited generalized-likelihood ratio scheme. Discussion on the two aspects of quadratic detection schemes; Assumptions made on the detection schemes; Conclusion.

The problem of quickest detection of a change in the mean of a sequence of independent observations is studied. The pre-change observations are assumed to be stationary, while the post-change observations are allowed to be non-stationary. The case where the pre-change distribution is known is studied first, and then the extension where only the mean and variance of the pre-change distribution are known. No knowledge of the post-change distributions is assumed other than that the means of the observations are above some pre-specified threshold larger than the pre-change mean. For the case where the pre-change distribution is known, a test is derived that asymptotically minimizes the worst-case detection delay over all possible post-change distributions, as the false alarm rate goes to zero. Towards deriving this asymptotically optimal test, some new results are provided for the general problem of asymptotic minimax robust quickest change detection in non-stationary settings. Then, the limiting form of the optimal test is studied as the gap between the pre- and post-change means goes to zero, called the Mean-Change Test (MCT). It is shown that the MCT can be designed with only knowledge of the mean and variance of the pre-change distribution. The performance of the MCT is also characterized when the mean gap is moderate, under the additional assumption that the distributions of the observations have bounded support. The analysis is validated through numerical results for detecting a change in the mean of a beta distribution. The use of the MCT in monitoring pandemics is also demonstrated. [ABSTRACT FROM AUTHOR]

Offline reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main methods are used: imitation learning which is suitable for expert datasets, and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these two extremes and the exact data composition is usually unknown. To bridge this gap, we present a new offline RL framework, called single-policy concentrability, that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. Under this new framework, we ask: can one develop an algorithm that achieves a minimax optimal rate adaptive to unknown data composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL. We study finite-sample properties of LCB as well as information-theoretic limits in multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in both contextual bandits and RL, LCB achieves a fast convergence rate for nearly-expert datasets, analogous to the one achieved by imitation learning, contrary to the slow rate achieved in offline RL. In contextual bandits, we prove that LCB is adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning to offline RL. We further show that LCB is almost adaptively optimal in MDPs. [ABSTRACT FROM AUTHOR]

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes. [ABSTRACT FROM AUTHOR]

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios. [ABSTRACT FROM AUTHOR]

Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditional block codes and are thus especially appealing for delay sensitive applications. Existing works on streaming code performance either focused on the asymptotic error-exponent analyses, or on the optimal code construction under deterministic adversarial channel models. In contrast, this work analyzes the exact error probability of random linear streaming codes (RLSCs) in the large field size regime over the stochastic i.i.d. symbol erasure channel model. A closed-form expression of the error probability of large-field-size RLSCs is derived under, simultaneously, the finite memory length and decoding deadline constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40–48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2–10% delay reduction). [ABSTRACT FROM AUTHOR]

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex $X$ at layer 0, and $k + 1$ vertices at layer $k \geq 1$ , which are at a distance of $k$ from $X$. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, $X$ is given a uniform random bit. At time $k \geq 1$ , each vertex in layer $k$ receives transmitted bits from its parents in layer $k-1$ , where the bits pass through independent binary symmetric channels with common crossover probability $\delta \in \left({0,\frac {1}{2}}\right)$ during the process of transmission. Then, each vertex at layer $k$ with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover $X$ with probability of error better than $\frac {1}{2}$ from all vertices at layer $k$ as $k \rightarrow \infty $. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time $k$ to $k+1$. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level $\delta $ and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of $X$ is impossible for any $\delta \in \left({0,\frac {1}{2}}\right)$ provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering $X$ for any $\delta \in \left({0,\frac {1}{2}}\right)$ when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of $\delta $ via linear programming. [ABSTRACT FROM AUTHOR]

Detection of the number of signals corrupted by high-dimensional noise is a fundamental problem in signal processing and statistics. This paper focuses on a general setting where the high-dimensional noise has an unknown complicated heterogeneous variance structure. We propose a sequential test which utilizes the edge singular values (i.e., the largest few singular values) of the data matrix. It also naturally leads to a consistent sequential testing estimate of the number of signals. We describe the asymptotic distribution of the test statistic in terms of the Tracy-Widom distribution. The test is shown to be accurate and have full power against the alternative, both theoretically and numerically. The theoretical analysis relies on establishing the Tracy-Widom law for a large class of Gram type random matrices with non-zero means and completely arbitrary variance profiles, which can be of independent interest. [ABSTRACT FROM AUTHOR]