Two channels are equivalent if their maximum likelihood (ML) decoders coincide for every code. We show that this equivalence relation partitions the space of channels into a generalized hyperplane arrangement. With this, we define a coding distance between channels in terms of their ML-decoders which is meaningful from the decoding point of view, in the sense that the closer two channels are, the larger is the probability of them sharing the same ML-decoder. We give explicit formulas for these probabilities.
Our approach to study the geometry of the space of channels has an intersection with the concept of , as introduced by Shannon @cite_2 and as presented, for example, by Makur and Polyanskiy @cite_12 . Using the notation of Makur and Polyanskiy, given two channels with transition matrices @math and @math of size @math and @math respectively, with @math and @math , one says that @math @math if there are two families @math and @math of channels (with @math being an @math transition matrix and @math an @math transition matrix) and probability mass function @math over the set @math such that [ Q= k=1 ^ m g ( k ) B_ k PA_ k . ]
@cite_12 @cite_2
2537174396 2011360117
This paper considers recovering @math -dimensional vectors @math , and @math from their circular convolutions @math . The vector @math is assumed to be @math -sparse in a known basis that is spread out in the Fourier domain, and each input @math is a member of a known @math -dimensional random subspace. We prove that whenever @math , the problem can be solved effectively by using only the nuclear-norm minimization as the convex relaxation, as long as the inputs are sufficiently diverse and obey @math . By “diverse inputs,” we mean that the @math ’s belong to different, generic subspaces. To the best of our knowledge, this is the first theoretical result on blind deconvolution where the subspace to which @math belongs is not fixed but needs to be determined. We discuss the result in the context of multipath channel estimation in wireless communications. Both the fading coefficients and the delays in the channel impulse response @math are unknown. The encoder codes the @math -dimensional message vectors randomly and then transmits coded messages @math ’s over a fixed channel one after the other. The decoder then discovers all of the messages and the channel response when the number of samples taken for each received message are roughly greater than @math , and the number of messages is roughly at least @math . We consider the problem of estimating the unknown response function in the multichannel deconvolution model with a boxcar-like kernel which is of particular interest in signal processing. It is known that, when the number of channels is finite, the precision of reconstruction of the response function increases as the number of channels @math grow (even when the total number of observations @math for all channels @math remains constant) and this requires that the parameter of the channels form a Badly Approximable @math -tuple. Recent advances in data collection and recording techniques made it of urgent interest to study the case when the number of channels @math grow with the total number of observations @math . However, in real-life situations, the number of channels @math usually refers to the number of physical devices and, consequently, may grow to infinity only at a slow rate as @math . When @math grows slowly as @math increases, we develop a procedure for the construction of a Badly Approximable @math -tuple on a specified interval, of a non-asymptotic length, together with a lower bound associated with this @math -tuple, which explicitly shows its dependence on @math as @math is growing. This result is further used for the evaluation of the @math -risk of the suggested adaptive wavelet thresholding estimator of the unknown response function and, furthermore, for the choice of the optimal number of channels @math which minimizes the @math -risk.