Search

Consider the compressed sensing setup where the support $\mathbf {s}^{\ast}$ of an $m$ -sparse $d$ -dimensional signal $\mathbf {x}$ is to be recovered from $n$ linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate $\mathbf {s}_{\text {in}}$ of the true support $\mathbf {s}^{\ast}$ , and outputs a refined support estimate $\mathbf {s}_{\text {out}}$. We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is $\mathbf {s}_{\text {out}}\supseteq \mathbf {s}^{\ast} $. These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in $m$ number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is ${\mathcal{O}}(m n d)$. Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE’s support recovery performance lies between OMP and BP. These results show that LiRE can be used generically, on top of any suboptimal baseline support recovery algorithm, to improve support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Alternatively, LiRE may be used as a standalone support recovery algorithm that is competitive with respect to OMP. [ABSTRACT FROM AUTHOR]

The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint. [ABSTRACT FROM AUTHOR]

This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength. [ABSTRACT FROM AUTHOR]

In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times. [ABSTRACT FROM AUTHOR]

The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay—the elapsed time between when information is available at the transmitter and when it is decoded—and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength $n$ , the second-order term in the maximum rate expansion is of order $\Theta (1/\rho)$ for any sampling rate $\rho =O(1/\sqrt {n})$ (and $\rho =\omega (1/n)$ for otherwise reliable communication is impossible). Instead, if $\rho =\omega (1/\sqrt {n})$ , then the second-order term is the same as under full sampling and is given by a standard $\Theta (\sqrt {n})$ term. However, if the delay constraint is only slightly relaxed to $n(1+o(1))$ , then the above order transition (for $\rho =O(1/\sqrt {n})$ and $\rho =\omega (1/\sqrt {n})$) vanishes and the second-order term remains the same as under full sampling for any $\rho =\omega (1/n)$. [ABSTRACT FROM AUTHOR]

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information was recently derived for bursty communication when information is available infrequently at random times at the transmitter. Furthermore, it was shown that even if the receiver is constrained to sample only a fraction $\rho \in ~(0,1]$ of the channel outputs, there is no capacity penalty. That is, for any strictly positive sampling rate $\rho $ , the asynchronous capacity per unit cost is the same as under full sampling, i.e., when $\rho =1$ . Moreover, there is no penalty in terms of decoding delay. These results are asymptotic in nature, considering the limit as the number $B$ of bits to be transmitted tends to infinity, while the sampling rate $\rho $ remains fixed. A natural question is then whether the sampling rate $\rho (B)$ can drop to zero without introducing a capacity (or delay) penalty compared with full sampling. We answer this question affirmatively. The main result of this paper is an essentially tight characterization of the minimum sampling rate. We show that any sampling rate that grows at least as fast as $\omega (1/B)$ is achievable, while any sampling rate smaller than $o(1/B)$ yields unreliable communication. The key ingredient in our improved achievability result is a new, multi-phase adaptive sampling scheme for locating transient changes, which we believe may be of independent interest for certain change-point detection problems. [ABSTRACT FROM PUBLISHER]

The construction of deletion codes for the editing metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of lattices’ translates. These lattices, in turn, are obtained from Construction A applied to binary codes and \mathbb Z4 –codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices. For any fixed number of deletions, provided the number of runs is large enough our method supplies a correction technique. For fixed number of runs and binary sequence length large our lattice construction is shown to be tight up to constants. [ABSTRACT FROM PUBLISHER]

This paper establishes the capacity region for a class of source coding function computation setups, where sources of information are available at the nodes of a tree and where a function of these sources must be computed at its root. The capacity region holds for any function as long as the sources’ joint distribution satisfies a certain Markov criterion. This criterion is met, in particular, when the sources are independent. This result recovers the capacity regions of several function computation setups. These include the point-to-point communication setting with arbitrary sources, the noiseless multiple access network with conditionally independent sources, and the cascade network with Markovian sources. [ABSTRACT FROM PUBLISHER]

The minimum energy, and, more generally, the minimum cost, to transmit 1 bit of information was recently derived for bursty communication when the information is available infrequently at random times at the transmitter. This result assumes that the receiver is always in the listening mode and samples all channel outputs until it makes a decision. Since sampling is in practice one of the receiver’s most energy consuming functions, a natural question is to evaluate capacity per unit cost when the receiver is sampling constrained. This paper investigates such a setting where the receiver can sample only a given fraction $ \rho \in (0, 1]$ of the channel outputs. It is shown that regardless of $ \rho > 0$ , the asynchronous capacity per unit cost is the same as under full sampling, i.e., when $ \rho = 1$ . Moreover, a sparse output sampling does not even impact decoding delay—the elapsed time between when information is available and when it is decoded. Hence, surprisingly, it suffices to sample an arbitrarily small fraction of the channel outputs and yet achieve the same (asymptotic) performance as under full output sampling. [ABSTRACT FROM AUTHOR]

The capacity per unit cost, or, equivalently, the minimum cost to transmit one bit, is a well-studied quantity under the assumption of full synchrony between the transmitter and the receiver. In many applications, such as sensor networks, transmissions are very bursty, with amounts of bits arriving infrequently at random times. In such scenarios, the cost of acquiring synchronization is significant and one is interested in the fundamental limits on communication without assuming a priori synchronization. In this paper, the minimum cost to transmit B bits of information asynchronously is shown to be equal to (B + \bar H) ksync, where ksync is the synchronous minimum cost per bit and \bar H is a measure of timing uncertainty equal to the entropy for most reasonable arrival time distributions. This result holds when the transmitter can stay idle at no cost and is a particular case of a general result which holds for arbitrary cost functions. [ABSTRACT FROM AUTHOR]

Several aspects of the problem of asynchronous point-to-point communication without feedback are developed when the source is highly intermittent. In the system model of interest, the codeword is transmitted at a random time within a prescribed window whose length corresponds to the level of asynchronism between the transmitter and the receiver. The decoder operates sequentially and communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. For such systems, general upper and lower bounds on capacity as a function of the level of asynchronism are established, and are shown to coincide in some nontrivial cases. From these bounds, several properties of this asynchronous capacity are derived. In addition, the performance of training-based schemes is investigated. It is shown that such schemes, which implement synchronization and information transmission on separate degrees of freedom in the encoding, cannot achieve the asynchronous capacity in general, and that the penalty is particularly significant in the high-rate regime. [ABSTRACT FROM AUTHOR]

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 maximum size of a binary code is studied as a function of its length n, minimum distance d, and minimum codeword weight \ssi w. This function B(n,d,\ssi w) is first characterized in terms of its exponential growth rate in the limit n\rightarrow\infty for fixed \delta=d/n and \omega=\ssi w/n. The exponential growth rate of B(n,d,\ssi w) is shown to be equal to the exponential growth rate of A(n,d) for 0\leq\omega\leq 1/2, and equal to the exponential growth rate of A(n,d,\ssi w) for 1/2<\omega\leq 1. Second, analytic and numerical upper bounds on B(n,d,\ssi w) are derived using the semidefinite programming (SDP) method. These bounds yield a nonasymptotic improvement of the second Johnson bound and are tight for certain values of the parameters. [ABSTRACT FROM AUTHOR]

Burnashev in 1976 gave an exact expression for the reliability function of a discrete memoryless channel (DMC) with noiseless feedback. A coding scheme that achieves this exponent needs, in general, to know the statistics of the channel. Suppose now that the coding scheme is designed knowing only that the channel belongs to a family Q of DMCs. Is there a coding scheme with noiseless feedback that achieves Burnashev's exponent uniformly over Q at a nontrivial rate? We answer the question in the affirmative for two families of channels (binary symmetric, and Z). For these families we show that, for any given fraction, there is a feedback coding strategy such that for any member of the family: i) guarantees this fraction of its capacity as rate, and ii) guarantees the corresponding Burnashev's exponent. Therefore, for these families, in terms of delay and error probability, the knowledge of the channel becomes asymptotically irrelevant in feedback code design: there are blind schemes that perform as well as the best coding scheme designed with the foreknowledge of the channel under use. However, a converse result shows that, in general, even for families that consist of only two channels, such blind schemes do not exist. [ABSTRACT FROM AUTHOR]

We consider a scalar additive channel æ → æ + N whose input is amplitude constrained. By extending Smith's argument, we derive a sufficient condition on noise probability density functions (pdfs) that guarantee finite support for the associated capacity-achieving distribution(s). [ABSTRACT FROM AUTHOR]