Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlmost exact analysis of soft covering lemma via large deviation
50
0
0.0
(
0
)
Added by
Mohammad Hossein Yassaee
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Mohammad Hossein Yassaee
Ask ChatGPT about the research
No Arabic abstract
This paper investigates the soft covering lemma under both the relative entropy and the total variation distance as the measures of deviation. The exact order of the expected deviation of the random i.i.d. code for the soft covering problem problem, is determined. The proof technique used in this paper significantly differs from the previous techniques for deriving exact exponent of the soft covering lemma. The achievability of the exact order follows from applying the change of measure trick (which has been broadly used in the large deviation) to the known one-shot bounds in the literature. For the ensemble converse, some new inequalities of independent interest derived and then the change of measure trick is applied again. The exact order of the total variation distance is similar to the exact order of the error probability, thus it adds another duality between the channel coding and soft covering. Finally, The results of this paper are valid for any memoryless channels, not only channels with finite alphabets.
rate research
Read More
Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in high dimensional multi-antenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the computation of its branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the ISS-MA provides a better performance-complexity trade-off than existing soft-input soft-output detection algorithms.
Let G be a finite strongly connected aperiodic directed graph in which each edge carries a label from a finite alphabet A. Then G induces a trellis coded quantizer for encoding an alphabet A memoryless source. A source sequence of long finite length is encoded by finding a path in G of that length whose sequence of labels is closest in Hamming distance to the source sequence; finding the minimum distance path is a dynamic programming problem that is solved using the Viterbi algorithm. We show how a Markov chain can be used to obtain a closed form expression for the asymptotic expected Hamming distortion per sample that results as the number of encoded source samples increases without bound.
Exact recovery of $K$-sparse signals $x in mathbb{R}^{n}$ from linear measurements $y=Ax$, where $Ain mathbb{R}^{mtimes n}$ is a sensing matrix, arises from many applications. The orthogonal matching pursuit (OMP) algorithm is widely used for reconstructing $x$. A fundamental question in the performance analysis of OMP is the characterizations of the probability of exact recovery of $x$ for random matrix $A$ and the minimal $m$ to guarantee a target recovery performance. In many practical applications, in addition to sparsity, $x$ also has some additional properties. This paper shows that these properties can be used to refine the answer to the above question. In this paper, we first show that the prior information of the nonzero entries of $x$ can be used to provide an upper bound on $|x|_1^2/|x|_2^2$. Then, we use this upper bound to develop a lower bound on the probability of exact recovery of $x$ using OMP in $K$ iterations. Furthermore, we develop a lower bound on the number of measurements $m$ to guarantee that the exact recovery probability using $K$ iterations of OMP is no smaller than a given target probability. Finally, we show that when $K=O(sqrt{ln n})$, as both $n$ and $K$ go to infinity, for any $0<zetaleq 1/sqrt{pi}$, $m=2Kln (n/zeta)$ measurements are sufficient to ensure that the probability of exact recovering any $K$-sparse $x$ is no lower than $1-zeta$ with $K$ iterations of OMP. For $K$-sparse $alpha$-strongly decaying signals and for $K$-sparse $x$ whose nonzero entries independently and identically follow the Gaussian distribution, the number of measurements sufficient for exact recovery with probability no lower than $1-zeta$ reduces further to $m=(sqrt{K}+4sqrt{frac{alpha+1}{alpha-1}ln(n/zeta)})^2$ and asymptotically $mapprox 1.9Kln (n/zeta)$, respectively.
The orthogonal matching pursuit (OMP) algorithm is a commonly used algorithm for recovering $K$-sparse signals $xin mathbb{R}^{n}$ from linear model $y=Ax$, where $Ain mathbb{R}^{mtimes n}$ is a sensing matrix. A fundamental question in the performance analysis of OMP is the characterization of the probability that it can exactly recover $x$ for random matrix $A$. Although in many practical applications, in addition to the sparsity, $x$ usually also has some additional property (for example, the nonzero entries of $x$ independently and identically follow the Gaussian distribution), none of existing analysis uses these properties to answer the above question. In this paper, we first show that the prior distribution information of $x$ can be used to provide an upper bound on $|x|_1^2/|x|_2^2$, and then explore the bound to develop a better lower bound on the probability of exact recovery with OMP in $K$ iterations. Simulation tests are presented to illustrate the superiority of the new bound.
The list-decodable code has been an active topic in theoretical computer science since the seminal papers of M. Sudan and V. Guruswami in 1997-1998. There are general result about the Johnson radius and the list-decoding capacity theorem for random codes. However few results about general constraints on rates, list-decodable radius and list sizes for list-decodable codes have been obtained. In this paper we show that rates, list-decodable radius and list sizes are closely related to the classical topic of covering codes. We prove new simple but strong upper bounds for list-decodable codes based on various covering codes. Then any good upper bound on the covering radius imply a good upper bound on the size of list-decodable codes. Hence the list-decodablity of codes is a strong constraint from the view of covering codes. Our covering code upper bounds for $(d,1)$ list decodable codes give highly non-trivial upper bounds on the sizes of codes with the given minimum Hamming distances. Our results give exponential improvements on the recent generalized Singleton upper bound of Shangguan and Tamo in STOC 2020, when the code lengths are very large. The asymptotic forms of covering code bounds can partially recover the list-decoding capacity theorem, the Blinovsky bound and the combinatorial bound of Guruswami-H{aa}stad-Sudan-Zuckerman. We also suggest to study the combinatorial covering list-decodable codes as a natural generalization of combinatorial list-decodable codes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
