اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLocalization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
52
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Localizing a cloud of points from noisy measurements of a subset of pairwise distances has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. In [1], Drineas et al. proposed a natural two-stage approach, named SVD-MDS, for this purpose. This approach consists of a low-rank matrix completion algorithm, named SVD-Reconstruct, to estimate random missing distances, and the classic multidimensional scaling (MDS) method to estimate the positions of nodes. In this paper, we present a detailed analysis for this method. More specifically, we first establish error bounds for Euclidean distance matrix (EDM) completion in both expectation and tail forms. Utilizing these results, we then derive the error bound for the recovered positions of nodes. In order to assess the performance of SVD-Reconstruct, we present the minimax lower bound of the zero-diagonal, symmetric, low-rank matrix completion problem by Fanos method. This result reveals that when the noise level is low, the SVD-Reconstruct approach for Euclidean distance matrix completion is suboptimal in the minimax sense; when the noise level is high, SVD-Reconstruct can achieve the optimal rate up to a constant factor.
قيم البحث
اقرأ أيضاً
In this paper, we propose a mechanism on the constructions of MDS codes with arbitrary dimensions of Euclidean hulls. Precisely, we construct (extended) generalized Reed-Solomon(GRS) codes with assigned dimensions of Euclidean hulls from self-orthogo
nal GRS codes. It turns out that our constructions are more general than previous works on Euclidean hulls of (extended) GRS codes.
In this paper, a criterion of MDS Euclidean self-orthogonal codes is presented. New MDS Euclidean self-dual codes and self-orthogonal codes are constructed via this criterion. In particular, among our constructions, for large square $q$, about $frac{
1}{8}cdot q$ new MDS Euclidean (almost) self-dual codes over $F_q$ can be produced. Moreover, we can construct about $frac{1}{4}cdot q$ new MDS Euclidean self-orthogonal codes with different even lengths $n$ with dimension $frac{n}{2}-1$.
The parameters of a $q$-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further stu
dy on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed.
In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out tha
t the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length n > q + 1 are also obtained.
Streaming codes represent a packet-level FEC scheme for achieving reliable, low-latency communication. In the literature on streaming codes, the commonly-assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-constrained, slidi
ng-window (DCSW) channel model that can introduce either random or burst erasures. The known streaming codes that are rate optimal over the DCSW channel model are constructed by diagonally embedding a scalar block code across successive packets. These code constructions have field size that is quadratic in the delay parameter $tau$ and have a somewhat complex structure with an involved decoding procedure. This led to the introduction of simple streaming (SS) codes in which diagonal embedding is replaced by staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a burst of erasures and makes it possible to construct near-rate-optimal streaming codes using Maximum Distance Separable (MDS) code having linear field size. The present paper takes this development one step further, by retaining the staggered-diagonal feature, but permitting the placement of more than one code symbol from a given scalar codeword within each packet. These generalized, simple streaming codes allow us to improve upon the rate of SS codes, while retaining the simplicity of working with MDS codes. We characterize the maximum code rate of streaming codes under a constraint on the number of contiguous packets over which symbols of the underlying scalar code are dispersed. Such a constraint leads to simplified code construction and reduced-complexity decoding.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
