This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by $t$-criss-cross deletions defined as any combination of $t_r$ row and $t_c$ column deletions such that $t_r + t_c = t$ for a given $t$. We show an equivalence between correcting $t$-criss-cross deletions and $t$-criss-cross insertions and show that a code correcting $t$-criss-cross insertions/deletions has redundancy at least $tn + t \log n - \log(t!)$. Then, we present an existential construction of $t$-criss-cross insertion/deletion correcting code with redundancy bounded from above by $tn + \mathcal{O}(t^2 \log^2 n)$. The main ingredients of the presented code construction are systematic binary $t$-deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient.
相關內容
In this paper, several classes of three-weight ternary linear codes from non-weakly regular dual-bent functions are constructed based on a generic construction method. Instead of the whole space, we use the subspaces $B_+(f)$ or $B_-(f)$ associated with a ternary non-weakly regular dual-bent function $f$. Unusually, we use the pre-image sets of the dual function $f^*$ in $B_+(f)$ or $B_-(f)$ as the defining sets of the corresponding codes. Since the size of the defining sets of the constructed codes is flexible, it enables us to construct several codes with different parameters for a fixed dimension. We represent the weight distribution of the constructed codes. We also give several examples.
We improve the bound on K\"uhnel's problem to determine the smallest $n$ such that the $k$-skeleton of an $n$-simplex $\Delta_n^{(k)}$ does not embed into a compact PL $2k$-manifold $M$ by showing that if $\Delta_n^{(k)}$ embeds into $M$, then $n\leq (2k+1)+(k+1)\beta_k(M;\mathbb Z_2)$. As a consequence we obtain improved Radon and Helly type results for set systems in such manifolds. Our main tool is a new description of an obstruction for embeddability of a $k$-complex $K$ into a compact PL $2k$-manifold $M$ via the intersection form on $M$. In our approach we need that for every map $f\colon K\to M$ the restriction to the $(k-1)$-skeleton of $K$ is nullhomotopic. In particular, this condition is satisfied in interesting cases if $K$ is $(k-1)$-connected, for example a $k$-skeleton of $n$-simplex, or if $M$ is $(k-1)$-connected. In addition, if $M$ is $(k-1)$-connected and $k\geq 3$, the obstruction is complete, meaning that a $k$-complex $K$ embeds into $M$ if and only if the obstruction vanishes. For trivial intersection forms, our obstruction coincides with the standard van Kampen obstruction. However, if the form is non-trivial, the obstruction is not linear but rather 'quadratic' in a sense that it vanishes if and only if certain system of quadratic diophantine equations is solvable. This may potentially be useful in attacking algorithmic decidability of embeddability of $k$-complexes into PL $2k$-manifolds.
This technical report is devoted to the continuous estimation of an epsilon-assignment. Roughly speaking, an epsilon assignment between two sets V1 and V2 may be understood as a bijective mapping between a sub part of V1 and a sub part of V2 . The remaining elements of V1 (not included in this mapping) are mapped onto an epsilon pseudo element of V2 . We say that such elements are deleted. Conversely, the remaining elements of V2 correspond to the image of the epsilon pseudo element of V1. We say that these elements are inserted. As a result our method provides a result similar to the one of the Sinkhorn algorithm with the additional ability to reject some elements which are either inserted or deleted. It thus naturally handles sets V1 and V2 of different sizes and decides mappings/insertions/deletions in a unified way. Our algorithms are iterative and differentiable and may thus be easily inserted within a backpropagation based learning framework such as artificial neural networks.
優化器
·
A code $\mathcal{C} \subseteq \{0, 1, 2\}^n$ is said to be trifferent with length $n$ when for any three distinct elements of $\mathcal{C}$ there exists a coordinate in which they all differ. Defining $\mathcal{T}(n)$ as the maximum cardinality of trifferent codes with length $n$, $\mathcal{T}(n)$ is unknown for $n \ge 5$. In this note, we use an optimized search algorithm to show that $\mathcal{T}(5) = 10$ and $\mathcal{T}(6) = 13$.
We show that solution to the Hermite-Pad\'{e} type I approximation problem leads in a natural way to a subclass of solutions of the Hirota (discrete Kadomtsev-Petviashvili) system and of its adjoint linear problem. Our result explains the appearence of various ingredients of the integrable systems theory in application to multiple orthogonal polynomials, numerical algorthms, random matrices, and in other branches of mathematical physics and applied mathematics where the Hermite-Pad\'{e} approximation problem is relevant. We present also the geometric algorithm, based on the notion of Desargues maps, of construction of solutions of the problem in the projective space over the field of rational functions. As a byproduct we obtain the corresponding generalization of the Wynn recurrence. We isolate the boundary data of the Hirota system which provide solutions to Hermite-Pad\'{e} problem showing that the corresponding reduction lowers dimensionality of the system. In particular, we obtain certain equations which, in addition to the known ones given by Paszkowski, can be considered as direct analogs of the Frobenius identities. We study the place of the reduced system within the integrability theory, which results in finding multidimensional (in the sense of number of variables) extension of the discrete-time Toda chain equations.
Motivated by applications to the theory of rank-metric codes, we study the problem of estimating the number of common complements of a family of subspaces over a finite field in terms of the cardinality of the family and its intersection structure. We derive upper and lower bounds for this number, along with their asymptotic versions as the field size tends to infinity. We then use these bounds to describe the general behaviour of common complements with respect to sparseness and density, showing that the decisive property is whether or not the number of spaces to be complemented is negligible with respect to the field size. By specializing our results to matrix spaces, we obtain upper and lower bounds for the number of MRD codes in the rank metric. In particular, we answer an open question in coding theory, proving that MRD codes are sparse for all parameter sets as the field size grows, with only very few exceptions. We also investigate the density of MRD codes as their number of columns tends to infinity, obtaining a new asymptotic bound. Using properties of the Euler function from number theory, we then show that our bound improves on known results for most parameter sets. We conclude the paper by establishing general structural properties of the density function of rank-metric codes.
In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over $\mathbb{F}_q$, for $q=\text{poly}(1/\varepsilon)$, that can efficiently decode from a $\delta$ fraction of insdel errors and have rate $(1-4\delta)/8-\varepsilon$. We also show that by allowing codes over $\mathbb{F}_{q^2}$ that are linear over $\mathbb{F}_q$, we can improve the rate to $(1-\delta)/4-\varepsilon$ while not sacrificing efficiency. Using this latter result, we construct fully linear codes over $\mathbb{F}_2$ that can efficiently correct up to $\delta < 1/54$ fraction of deletions and have rate $R = (1-54\cdot \delta)/1216$. Cheng, Guruswami, Haeupler, and Li [CGHL21] constructed codes with (extremely small) rates bounded away from zero that can correct up to a $\delta < 1/400$ fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the half-Singleton bound (proved in [CGHL21]) over small fields. Thus, our results significantly improve their construction and get much closer to the bound.
A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawing of $G+e$ extending $D(G)$. As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of $G$ can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles $\mathcal{A}$ and a pseudosegment $\sigma$, it can be decided in polynomial time whether there exists a pseudocircle $\Phi_\sigma$ extending $\sigma$ for which $\mathcal{A}\cup\{\Phi_\sigma\}$ is again an arrangement of pseudocircles.
Large-scale simulations of time-dependent problems generate a massive amount of data and with the explosive increase in computational resources the size of the data generated by these simulations has increased significantly. This has imposed severe limitations on the amount of data that can be stored and has elevated the issue of input/output (I/O) into one of the major bottlenecks of high-performance computing. In this work, we present an in situ compression technique to reduce the size of the data storage by orders of magnitude. This methodology is based on time-dependent subspaces and it extracts low-rank structures from multidimensional streaming data by decomposing the data into a set of time-dependent bases and a core tensor. We derive closed-form evolution equations for the core tensor as well as the time-dependent bases. The presented methodology does not require the data history and the computational cost of its extractions scales linearly with the size of data -- making it suitable for large-scale streaming datasets. To control the compression error, we present an adaptive strategy to add/remove modes to maintain the reconstruction error below a given threshold. We present four demonstration cases: (i) analytical example, (ii) incompressible unsteady reactive flow, (iii) stochastic turbulent reactive flow, and (iv) three-dimensional turbulent channel flow.
Motion artifacts are a primary source of magnetic resonance (MR) image quality deterioration with strong repercussions on diagnostic performance. Currently, MR motion correction is carried out either prospectively, with the help of motion tracking systems, or retrospectively by mainly utilizing computationally expensive iterative algorithms. In this paper, we utilize a novel adversarial framework, titled MedGAN, for the joint retrospective correction of rigid and non-rigid motion artifacts in different body regions and without the need for a reference image. MedGAN utilizes a unique combination of non-adversarial losses and a novel generator architecture to capture the textures and fine-detailed structures of the desired artifacts-free MR images. Quantitative and qualitative comparisons with other adversarial techniques have illustrated the proposed model's superior performance.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191