For the benefit of improved intermediate performance, recently online
fountain codes attract much research attention. However, there is a trade-off
between the intermediate performance and the full recovery overhead for online
fountain codes, which prevents them to be improved simultaneously. We analyze
this trade-off, and propose to improve both of these two performance. We first
propose a method called Online Fountain Codes without Build-up phase (OFCNB)
where the degree-1 coded symbols are transmitted at first and the build-up
phase is removed to improve the intermediate performance. Then we analyze the
performance of OFCNB theoretically. Motivated by the analysis results, we
propose Systematic Online Fountain Codes (SOFC) to further reduce the full
recovery overhead. Theoretical analysis shows that SOFC has better intermediate
performance, and it also requires lower full recovery overhead when the channel
erasure rate is lower than a constant. Simulation results verify the analyses
and demonstrate the superior performance of...

more |
pdf
| html
None.

mathITbot:
Jingxuan Huang, Zesong Fei, Congzhe Cao, Ming Xiao : Design and Analysis of Online Fountain Codes for Intermediate Performance https://t.co/jFOvVWnpLe https://t.co/ouck9arMDE

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

The aim of this work is to provide bounds connecting two probability measures
of the same event using R\'enyi $\alpha$-Divergences and Sibson's
$\alpha$-Mutual Information, a generalization of respectively the
Kullback-Leibler Divergence and Shannon's Mutual Information. A particular case
of interest can be found when the two probability measures considered are a
joint distribution and the corresponding product of marginals (representing the
statistically independent scenario). In this case, a bound using Sibson's
$\alpha-$Mutual Information is retrieved, extending a result involving Maximal
Leakage to general alphabets. These results have broad applications, from
bounding the generalization error of learning algorithms to the more general
framework of adaptive data analysis, provided that the divergences and/or
information measures used are amenable to such an analysis ({\it i.e.,} are
robust to post-processing and compose adaptively). The generalization error
bounds are derived with respect to high-probability events but a...

more |
pdf
| html
None.

Memoirs:
Robust Generalization via $\alpha$-Mutual Information. https://t.co/QFJSfB1O87

arxivml:
"Robust Generalization via $α$-Mutual Information",
Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa
https://t.co/kftkKML6Ut

mathITbot:
Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa : Robust Generalization via $α$-Mutual Information https://t.co/mSab7bFS7E https://t.co/OTRLfmecWJ

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

In this work, we consider private monomial computation (PMC) for replicated
noncolluding databases. In PMC, a user wishes to privately retrieve an
arbitrary multivariate monomial from a candidate set of monomials in $f$
messages over a finite field $\mathbb F_q$, where $q=p^k$ is a power of a prime
$p$ and $k \ge 1$, replicated over $n$ databases. We derive the PMC capacity
under a technical condition on $p$ and for asymptotically large $q$. The
condition on $p$ is satisfied, e.g., for large enough $p$. Also, we present a
novel PMC scheme for arbitrary $q$ that is capacity-achieving in the asymptotic
case above. Moreover, we present formulas for the entropy of a multivariate
monomial and for a set of monomials in uniformly distributed random variables
over a finite field, which are used in the derivation of the capacity
expression.

more |
pdf
| html
None.

mathITbot:
Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes : On the Capacity of Private Monomial Computation https://t.co/3LpWt9Rtmt https://t.co/3acKugt2pw

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

Due to its longevity and enormous information density, DNA is an attractive
medium for archival storage. In this work, we study the fundamental limits and
trade-offs of DNA-based storage systems by introducing a new channel model,
which we call the noisy shuffling-sampling channel. Motivated by current
technological constraints on DNA synthesis and sequencing, this model captures
three key distinctive aspects of DNA storage systems: (1) the data is written
onto many short DNA molecules; (2) the molecules are corrupted by noise during
synthesis and sequencing and (3) the data is read by randomly sampling from the
DNA pool. We provide capacity results for this channel under specific noise and
sampling assumptions and show that, in many scenarios, a simple index-based
coding scheme is optimal.

more |
pdf
| html
None.

mathITbot:
Ilan Shomorony, Reinhard Heckel : DNA-Based Storage: Models and Fundamental Limits https://t.co/j1xIU4Ay4j https://t.co/yZnHob1zeK

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

In this article, we consider the decoding problem of Grassmann codes using
majority logic. We show that for two points of the Grassmannian, there exists a
canonical path between these points once a complete flag is fixed. These paths
are used to construct a large set of parity checks orthogonal on a coordinate
of the code, resulting in a majority decoding algorithm.

more |
pdf
| html
None.

mathITbot:
Peter Beelen, Prasant Singh : Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes https://t.co/TSVkDR7bjE https://t.co/MurlvV9FXq

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Ensemble models are widely used to solve complex tasks by their decomposition
into multiple simpler tasks, each one solved locally by a single member of the
ensemble. Decoding of error-correction codes is a hard problem due to the curse
of dimensionality, leading one to consider ensembles-of-decoders as a possible
solution. Nonetheless, one must take complexity into account, especially in
decoding. We suggest a low-complexity scheme where a single member participates
in the decoding of each word. First, the distribution of feasible words is
partitioned into non-overlapping regions. Thereafter, specialized experts are
formed by independently training each member on a single region. A classical
hard-decision decoder (HDD) is employed to map every word to a single expert in
an injective manner. FER gains of up to 0.4dB at the waterfall region, and of
1.25dB at the error floor region are achieved for two BCH(63,36) and (63,45)
codes with cycle-reduced parity-check matrices, compared to the previous best
result of the paper "Active...

more |
pdf
| html
mathITbot:
Tomer Raviv, Nir Raviv, Yair Be'ery : Data-Driven Ensembles for Deep and Hard-Decision Hybrid Decoding https://t.co/wdAZqpvfe7 https://t.co/XrDcKZjtPa

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 4353

Unqiue Words: 1637

We study the duplication with transposition distance between strings of
length $n$ over a $q$-ary alphabet and their roots. In other words, we
investigate the number of duplication operations of the form $x = (abcd) \to y
= (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their
substrings, needed to get a $q$-ary string of length $n$ starting from the set
of strings without duplications. For exact duplication, we prove that the
maximal distance between a string of length at most $n$ and its root has the
asymptotic order $n/\log n$. For approximate duplication, where a
$\beta$-fraction of symbols may be duplicated incorrectly, we show that the
maximal distance has a sharp transition from the order $n/\log n$ to $\log n$
at $\beta=(q-1)/q$. The motivation for this problem comes from genomics, where
such duplications represent a special kind of mutation and the distance between
a given biological sequence and its root is the smallest number of
transposition mutations required to generate the sequence.

more |
pdf
| html
None.

mathITbot:
Nikita Polyanskii, Ilya Vorobyev : Duplication with transposition distance to the root for $q$-ary strings https://t.co/ipgguH4SK9 https://t.co/qF2jwgimo5

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

The Landweber algorithm defined on complex/real Hilbert spaces is a gradient
descent algorithm for linear inverse problems. Our contribution is to present a
novel method for accelerating convergence of the Landweber algorithm. In this
paper, we first extend the theory of the Chebyshev inertial iteration to the
Landweber algorithm on Hilbert spaces. An upper bound on the convergence rate
clarifies the speed of global convergence of the proposed method. The Chebyshev
inertial Landweber algorithm can be applied to wide class of signal recovery
problems on a Hilbert space including deconvolution for continuous signals. The
theoretical discussion developed in this paper naturally leads to a novel
practical signal recovery algorithm. As a demonstration, a MIMO detection
algorithm based on the projected Landweber algorithm is derived. The proposed
MIMO detection algorithm achieves much smaller symbol error rate compared with
the MMSE detector.

more |
pdf
| html
None.

mathITbot:
Tadashi Wadayama, Satoshi Takabe : Chebyshev Inertial Landweber Algorithm for Linear Inverse Problems https://t.co/BDQClBszga https://t.co/okaCr5CJt0

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

We show a general phenomenon of the constrained functional value for
densities satisfying general convexity conditions, which generalizes the
observation in Bobkov and Madiman (2011) that the entropy per coordinate in a
log-concave random vector in any dimension with given density at the mode has a
range of just 1. Specifically, for general functions $\phi$ and $\psi$, we
derive upper and lower bounds of density functionals taking the form $I_\phi(f)
= \int_{\mathbb{R}^n} \phi(f(x))dx$ assuming the convexity of $\psi^{-1}(f(x))$
for the density, and establish the tightness of these bounds under mild
conditions satisfied by most examples. We apply this result to the distributed
simulation of continuous random variables, and establish an upper bound of the
exact common information for $\beta$-concave joint densities, which is a
generalization of the log-concave densities in Li and El Gamal (2017).

more |
pdf
| html
None.

mathITbot:
Yanjun Han : Constrained Functional Value under General Convexity Conditions with Applications to Distributed Simulation https://t.co/hwako4eIBB https://t.co/JsrbBXWVik

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al.,
this paper presents algorithms for low-complexity sequential transmission of a
$k$-bit message over the binary symmetric channel (BSC) with full, noiseless
feedback. To lower complexity, this paper shows that the initial $k$ binary
transmissions can be sent before any feedback is required and groups the
messages with equal posteriors to reduce the number of posterior updates from
exponential in $k$ to linear in $k$. Simulations results demonstrate the
achievable rates for this full, noiseless feedback system approach capacity
rapidly as a function of $k$, significantly faster than the achievable rate
curve of Polyanskiy et al. for a stop feedback system.

more |
pdf
| html
None.

mathITbot:
Amaael Antonini, Hengjie Yang, Richard D. Wesel : Low Complexity Algorithms for Transmission of Short Blocks over the BSC with Full Feedback https://t.co/UjFET6BelO https://t.co/hteMop7sEr

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 255,370 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible