اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOptimal reconstruction systems for erasures and for the q-potential
260
0
0.0
(
0
)
تأليف
Pedro G. Massey
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce the $q$-potential as an extension of the Benedetto-Fickus frame potential, defined on general reconstruction systems and we show that protocols are the minimizers of this potential under certain restrictions. We extend recent results of B.G. Bodmann on the structure of optimal protocols with respect to 1 and 2 lost packets where the worst (normalized) reconstruction error is computed with respect to a compatible unitarily invariant norm. We finally describe necessary and sufficient (spectral) conditions, that we call $q$-fundamental inequalities, for the existence of protocols with prescribed properties by relating this problem to Klyachkos and Fultons theory on sums of hermitian operators.
قيم البحث
اقرأ أيضاً
This paper considers the transmission of an infinite sequence of messages (a streaming source) over a packet erasure channel, where every source message must be recovered perfectly at the destination subject to a fixed decoding delay. While the capac
ity of a channel that introduces only bursts of erasures is well known, only recently, the capacity of a channel with either one burst of erasures or multiple arbitrary erasures in any fixed-sized sliding window has been established. However, the codes shown to achieve this capacity are either non-explicit constructions (proven to exist) or explicit constructions that require large field size that scales exponentially with the delay. This work describes an explicit rate-optimal construction for admissible channel and delay parameters over a field size that scales only quadratically with the delay.
In this paper we consider two problems in frame theory. On the one hand, given a set of vectors $mathcal F$ we describe the spectral and geometrical structure of optimal completions of $mathcal F$ by a finite family of vectors with prescribed norms,
where optimality is measured with respect to majorization. In particular, these optimal completions are the minimizers of a family of convex functionals that include the mean square error and the Bendetto-Fickus frame potential. On the other hand, given a fixed frame $mathcal F$ we describe explicitly the spectral and geometrical structure of optimal frames $mathcal G$ that are in duality with $mathcal F$ and such that the Frobenius norms of their analysis operators is bounded from below by a fixed constant. In this case, optimality is measured with respect to submajorization of the frames operators. Our approach relies on the description of the spectral and geometrical structure of matrices that minimize submajorization on sets that are naturally associated with the problems above.
We present an extension of some results of higher order calculus of variations and optimal control to generalized functions. The framework is the category of generalized smooth functions, which includes Schwartz distributions, while sharing many nonl
inear properties with ordinary smooth functions. We prove the higher order Euler-Lagrange equations, the DAlembert principle in differential form, the du Bois-Reymond optimality condition and the Noethers theorem. We start the theory of optimal control proving a weak form of the Pontryagin maximum principle and the Noethers theorem for optimal control. We close with a study of a singularly variable length pendulum, oscillations damped by two media and the Pais-Uhlenbeck oscillator with singular frequencies.
The noisy broadcast model was first studied in [Gallager, TranInf88] where an $n$-character input is distributed among $n$ processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor b
roadcasts a single character, and each reception is corrupted independently at random with some probability $p$. [Gallager, TranInf88] gave an algorithm for all processors to learn the input in $O(loglog n)$ rounds with high probability. Later, a matching lower bound of $Omega(loglog n)$ was given in [Goyal, Kindler, Saks; SICOMP08]. We study a relaxed version of this model where each reception is erased and replaced with a `? independently with probability $p$. In this relaxed model, we break past the lower bound of [Goyal, Kindler, Saks; SICOMP08] and obtain an $O(log^* n)$-round algorithm for all processors to learn the input with high probability. We also show an $O(1)$-round algorithm for the same problem when the alphabet size is $Omega(mathrm{poly}(n))$.
Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential
of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating $f$ server crashes in an $n$-server system, SODA uses an $[n, k]$ MDS code with $k=n-f$, and incurs a total storage cost of $frac{n}{n-f}$. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by $O(f^2)$ and $frac{n}{n-f}(delta_w+1)$, where $delta_w$ denotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm, which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODA$_{text{err}}$, to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate $f$ server failures and $e$ error-prone coded elements, the SODA$_{text{err}}$ algorithm uses an $[n, k]$ MDS code such that $k=n-2e-f$. SODA$_{text{err}}$ also guarantees liveness and atomicity, while maintaining an optimized total storage cost of $frac{n}{n-f-2e}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
