信息论学术速递[1.10]
Update！H5支持摘要折叠，体验更佳！点击阅读原文访问arxivdaily.com，涵盖CS|物理|数学|经济|统计|金融|生物|电气领域，更有搜索、收藏等功能！
cs.IT信息论，共计7篇
【1】 The Efficiency of the ANS Entropy Encoding
标题：ANS熵编码的效率分析
链接：https://arxiv.org/abs/2201.02514
备注：15 pages, 5 figures, 2 algorithms
摘要：The Asymmetric Numeral Systems (ANS) is a class of entropy encoders by Duda
that had an immense impact on the data compression, substituting arithmetic and
Huffman coding. The optimality of ANS was studied by Duda et al. but the
precise asymptotic behaviour of its redundancy (in comparison to the entropy)
was not completely understood. In this paper we establish an optimal bound on
the redundancy for the tabled ANS (tANS), the most popular ANS variant. Given a
sequence $a_1,\ldots,a_n$ of letters from an alphabet $\{0,\ldots,\sigma-1\}$
such that each letter $a$ occurs in it $f_a$ times and $n=2^r$, the tANS
encoder using Duda's ``precise initialization'' to fill tANS tables transforms
this sequence into a bit string of length (frequencies are not included in the
encoding size): $$ \sum\limits_{a\in
[0..\sigma)}f_a\cdot\log\frac{n}{f_a}+O(\sigma+r), $$ where $O(\sigma + r)$ can
be bounded by $\sigma\log e+r$. The $r$-bit term is an encoder artifact
indispensable to ANS; the rest incurs a redundancy of $O(\frac{\sigma}{n})$
bits per letter. We complement this bound by a series of examples showing that
an $\Omega(\sigma+r)$ redundancy is necessary when $\sigma > n/3$, where
$\Omega(\sigma + r)$ is at least $\frac{\sigma-1}{4}+r-2$. We argue that
similar examples exist for any methods that distribute letters in tANS tables
using only the knowledge about frequencies. Thus, we refute Duda's conjecture
that the redundancy is $O(\frac{\sigma}{n^2})$ bits per letter.
We also propose a new variant of range ANS (rANS), called rANS with fixed
accuracy, that is parameterized by $k \ge 1$. In this variant the integer
division, which is unavoidable in rANS, is performed only in cases when its
result belongs to $[2^k..2^{k+1})$. Hence, the division can be computed by
faster methods provided $k$ is small. We bound the redundancy for the rANS with
fixed accuracy $k$ by $\frac{n}{2^k-1}\log e+r$.
【2】 On The Decoding Error Weight of One or Two Deletion Channels
标题：关于一个或两个删除信道的译码误码权重
链接：https://arxiv.org/abs/2201.02466
备注：arXiv admin note: text overlap with arXiv:2001.05582
摘要：This paper tackles two problems that are relevant to coding for insertions
and deletions. These problems are motivated by several applications, among them
is reconstructing strands in DNA-based storage systems. Under this paradigm, a
word is transmitted over some fixed number of identical independent channels
and the goal of the decoder is to output the transmitted word or some close
approximation of it. The first part of this paper studies the deletion channel
that deletes a symbol with some fixed probability $p$, while focusing on two
instances of this channel. Since operating the maximum likelihood (ML) decoder
in this case is computationally unfeasible, we study a slightly degraded
version of this decoder for two channels and its expected normalized distance.
We identify the dominant error patterns and based on these observations, it is
derived that the expected normalized distance of the degraded ML decoder is
roughly $\frac{3q-1}{q-1}p^2$, when the transmitted word is any $q$-ary
sequence and $p$ is the channel's deletion probability. We also study the cases
when the transmitted word belongs to the Varshamov Tenengolts (VT) code or the
shifted VT code. Additionally, the insertion channel is studied as well as the
case of two insertion channels. These theoretical results are verified by
corresponding simulations. The second part of the paper studies optimal
decoding for a special case of the deletion channel, the $k$-deletion channel,
which deletes exactly $k$ symbols of the transmitted word uniformly at random.
In this part, the goal is to understand how an optimal decoder operates in
order to minimize the expected normalized distance. A full characterization of
an efficient optimal decoder for this setup, referred to as the maximum
likelihood* (ML*) decoder, is given for a channel that deletes one or two
symbols.
【3】 Analytical calculation formulas for capacities of classical and classical-quantum channels
标题：经典信道和经典量子信道容量的解析计算公式
链接：https://arxiv.org/abs/2201.02450
摘要：We derive an analytical calculation formula for the channel capacity of a
classical channel without any iteration while its existing algorithms require
iterations and the number of iteration depends on the required precision level.
Hence, our formula is its first analytical formula without any iteration. We
apply the obtained formula to examples and see how the obtained formula works
in these examples. Then, we extend it to the channel capacity of a
classical-quantum (cq-) channel. Many existing studies proposed algorithms for
a cq-channel and all of them require iterations. Our extended analytical
algorithm have also no iteration and output the exactly optimum values.
【4】 Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory
标题：基于Bregman散度的em算法及其在经典和量子率失真理论中的应用
链接：https://arxiv.org/abs/2201.02447
摘要：We formulate em algorithm in the framework of Bregman divergence, which is a
general problem setting of information geometry. That is, we address the
minimization problem of the Bregman divergence between an exponential subfamily
and a mixture subfamily in a Bregman divergence system. Then, we show the
convergence and its speed under several conditions. We apply this algorithm to
rate distortion and its variants including the quantum setting, and show the
usefulness of our general algorithm.
【5】 Delay Alignment Modulation: Enabling Equalization-Free Single-Carrier Communication
标题：延迟对齐调制：实现无均衡单载波通信
链接：https://arxiv.org/abs/2201.02291
备注：5 pages, 6 figures
摘要：This paper proposes a novel broadband transmission technology, termed delay
alignment modulation (DAM), which enables the low-complexity equalization-free
single-carrier communication, yet without suffering from inter-symbol
interference (ISI). The key idea of DAM is to deliberately introduce
appropriate delays for information-bearing symbols at the transmitter side, so
that after propagating over the time-dispersive channel, all multi-path signal
components will arrive at the receiver simultaneously and constructively. We
first show that by applying DAM for the basic multiple-input single-output
(MISO) communication system, an ISI-free additive white Gaussian noise (AWGN)
system can be obtained with the simple zero-forcing (ZF) beamforming.
Furthermore, the more general DAM scheme is studied with the ISI-maximal-ratio
transmission (MRT) and the ISI-minimum mean-square error (MMSE) beamforming.
Simulation results are provided to show that when the channel is sparse and/or
the antenna dimension is large, DAM not only resolves the notorious practical
issues suffered by orthogonal frequency-division multiplexing (OFDM) such as
high peak-to-average-power ratio (PAPR), severe out-of-band (OOB) emission, and
vulnerability to carrier frequency offset (CFO), with low complexity, but also
achieves higher spectral efficiency due to the saving of guard interval
overhead.
【6】 Local and Global Convergence of General Burer-Monteiro Tensor Optimizations
标题：广义布里-蒙泰罗张量优化问题的局部收敛性和全局收敛性
链接：https://arxiv.org/abs/2201.02298
摘要：Tensor optimization is crucial to massive machine learning and signal
processing tasks. In this paper, we consider tensor optimization with a convex
and well-conditioned objective function and reformulate it into a nonconvex
optimization using the Burer-Monteiro type parameterization. We analyze the
local convergence of applying vanilla gradient descent to the factored
formulation and establish a local regularity condition under mild assumptions.
We also provide a linear convergence analysis of the gradient descent algorithm
started in a neighborhood of the true tensor factors. Complementary to the
local analysis, this work also characterizes the global geometry of the best
rank-one tensor approximation problem and demonstrates that for orthogonally
decomposable tensors the problem has no spurious local minima and all saddle
points are strict except for the one at zero which is a third-order saddle
point.
【7】 Well-Conditioned Linear Minimum Mean Square Error Estimation
标题：良态线性最小均方误差估计
链接：https://arxiv.org/abs/2201.02275
摘要：Computing linear minimum mean square error (LMMSE) filters is often ill
conditioned, suggesting that unconstrained minimization of the mean square
error is an inadequate principle for filter design. To address this, we first
develop a unifying framework for studying constrained LMMSE estimation
problems. Using this framework, we expose an important structural property of
all constrained LMMSE filters and show that they all involve an inherent
preconditioning step. This parameterizes all such filters only by their
preconditioners. Moreover, each filters is invariant to invertible linear
transformations of its preconditioner. We then clarify that merely constraining
the rank of the filters, leading to the well-known low-rank Wiener filter, does
not suitably address the problem of ill conditioning. Instead, we use a
constraint that explicitly requires solutions to be well conditioned in a
certain specific sense. We introduce two well-conditioned estimators and
evaluate their mean-squared-error performance. We show these two estimators
converge to the standard LMMSE filter as their truncated-power ratio converges
to zero, but more slowly than the low-rank Wiener filter in terms of scaling
law. This exposes the price for being well conditioned. We also show
quantitative results with historical VIX data to illustrate the performance of
our two well-conditioned estimators.
机器翻译，仅供参考
点击“阅读原文”获取带摘要的学术速递