Добірка наукової літератури з теми "Linear Subspace Codes"

Constant dimension subspace codes are subsets of the finite Grassmann Variety. Orbit codes are constant dimension subspace codes that arise as the orbit of subgroup of general linear group acting on subspaces in an ambient space. In particular, orbit codes of symplectic subgroup of the general linear group have been investigated recently. In this paper, we determine product of symplectic groups and its orbit code, and decoding algorithm of this code is considered.

The Sphere-packing bound, Singleton bound, Wang-Xing-Safavi-Naini bound, Johnson bound, and Gilbert-Varshamov bound on the subspace codesn+l,M,d,(m,1)qbased on subspaces of type(m,1)in singular linear spaceFq(n+l)over finite fieldsFqare presented. Then, we prove that codes based on subspaces of type(m,1)in singular linear space attain the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures inFq(n+l).

The existence is proved of a class of open quantum systems that admits a linear subspace [Formula: see text] of the space of states such that the restriction of the dynamical semigroup to the states built over [Formula: see text] is unitary. Such subspace allows for error-avoiding (noiseless) encoding of quantum information.

In this paper, we survey the main known constructions of Ferrers diagram rank-metric codes, and establish new results on a related conjecture by Etzion and Silberstein. We also give a sharp lower bound on the dimension of linear rank-metric anticodes with a given profile. Combining our results with the multilevel construction, we produce examples of subspace codes with the largest known cardinality for the given parameters. We also apply results from algebraic geometry to the study of the analogous problem over an algebraically closed field, proving that the bound by Etzion and Silberstein can be improved in this case, and providing a sharp bound for full-rank matrices.

In this paper, the Sphere-packing bound, Wang-Xing-Safavi-Naini bound, Johnson bound and Gilbert-Varshamov bound on the subspace code of length [Formula: see text], size [Formula: see text], minimum subspace distance [Formula: see text] based on [Formula: see text]-dimensional totally singular subspace in the [Formula: see text]-dimensional orthogonal space [Formula: see text] over finite fields [Formula: see text] of characteristic 2, denoted by [Formula: see text], are presented, where [Formula: see text] is a positive integer, [Formula: see text], [Formula: see text], [Formula: see text]. Then, we prove that [Formula: see text] codes attain the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures in [Formula: see text], where [Formula: see text] denotes the collection of all the [Formula: see text]-dimensional totally singular subspaces in the [Formula: see text]-dimensional orthogonal space [Formula: see text] over [Formula: see text] of characteristic 2. Finally, Gilbert-Varshamov bound and linear programming bound on the subspace code [Formula: see text] in [Formula: see text] are provided, where [Formula: see text] denotes the collection of all the totally singular subspaces in the [Formula: see text]-dimensional orthogonal space [Formula: see text] over [Formula: see text] of characteristic 2.

We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1-R-ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The alphabet size depends only ε and is nearly optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield . In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice “periodic” structure. To prune this subspace and obtain a good bound on the list size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets that are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspace-evasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e.) sets that leads to excellent list size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs , which were subsequently constructed explicitly and also found further applications in pseudorandomness. To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia–Stichtenoth tower of function fields. Combining this with pruning via h.s.e. sets yields codes list-decodable up to a 1-R-ε error fraction with list size bounded by O (1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made exp ( Õ (1/ε 2 )), which is not much worse than the lower bound of exp (Ω (1/ε)). The parameters we achieve are thus quite close to the existential bounds in all three aspects (error-correction radius, alphabet size, and list size) simultaneously. This construction is, however, Monte Carlo and the claimed list-decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O _ε ( N c ) for an absolute constant c , where N is the code’s block length. Using subspace designs instead for the pruning, our approach yields the first deterministic construction of an algebraic code family of rate R with efficient list decoding from 1-R-ε fraction of errors over an alphabet of constant size exp (Õ(1/ε 2 )). The list-size bound is upper bounded by a very slowly growing function of the block length N ; in particular, it is at most O(log ( r ) N ) (the r th iterated logarithm) for any fixed integer r . The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size.

Generative Adversarial Networks (GANs) have shown impressive gains in image synthesis. GAN inversion was recently studied to understand and utilize the knowledge it learns, where a real image is inverted back to a latent code and can thus be reconstructed by the generator. Although increasing the number of latent codes can improve inversion quality to a certain extent, we find that important details may still be neglected when performing feature composition over all the intermediate feature channels. To address this issue, we propose a Prior multi-Subspace Feature Composition (PmSFC) approach for high-fidelity inversion. Considering that the intermediate features are highly correlated with each other, we incorporate a self-expressive layer in the generator to discover meaningful subspaces. In this case, the features at a channel can be expressed as a linear combination of those at other channels in the same subspace. We perform feature composition separately in the subspaces. The semantic differences between them benefit the inversion quality, since the inversion process is regularized based on different aspects of semantics. In the experiments, the superior performance of PmSFC demonstrates the effectiveness of prior subspaces in facilitating GAN inversion together with extended applications in visual manipulation.

The modular representations of the FpWn-Specht modules( , )KSas linear codes is given in our paper [6], and the modular irreducible representations of the FpW4-submodules( , )pFNof the Specht modules pFS ( , )as linear codes where W4is the Weyl group of type B4is given in our paper [5]. In this paper we are concerning of finding the linear codes of the representations of the irreducible FpW4-submodules( , )pFNof the FpW4-modules( , )pFMfor each pair of partitions( , )of a positive integer n4, where FpGF(p) is the Galois field (finite field) of order p, and pis a prime number greater than or equal to 3. We will find in this paper a generator matrix of a subspace((2,1),(1))()pU representing the irreducible FpW4-submodules((2,1),(1))pFNof the FpW4-modules((2,1),(1))pF Mand give the linear code of ((2,1),(1))()pU for each prime number p greater than or equal to 3. Then we will give the linear codes of all the subspaces( , )()pUfor all pair of partitions( , )of a positive integer n4, and for each prime number p greater than or equal to 3.We mention that some of the ideas of this work in this paper have been influenced by that of Adalbert Kerber and Axel Kohnert [13], even though that their paper is about the symmetric group and this paper is about the Weyl groups of type Bn

The projective space $\mathbb{P}_q(n)$ of order $n$ over a finite field $\mathbb{F}_q$ is defined as the collection of all subspaces of the ambient space $\mathbb{F}_q^n$. The Grassmannian $\mathcal{G}_q(n, k)$ is the set of all members of $\mathbb{P}_q(n)$ with fixed dimension $k$. The subspace distance function, defined as $d_S(X, Y) = \dim(X+Y) - \dim(X \cap Y)$ serves as a suitable metric to turn the projective space $\mathbb{P}_q(n)$ into a metric space. A code in the projective space $\mathbb{P}_q(n)$ is a subset of $\mathbb{P}_q(n)$. Projective space has been shown previously by Koetter and Kschischang to be the ideal coding space for error and erasure correction in random network coding. Linear codes find huge applications in classical error-correction. The notion of linearity was introduced in codes in projective space recently. A subspace code $\mathcal{U}$ in $\mathbb{P}_q(n)$ that contains $\left\{ 0\right\}$ is linear if there exists a function $\boxplus : \mathcal{U} \times \mathcal{U} \rightarrow \mathcal{U}$ such that $(\mathcal{U}, \boxplus)$ is an abelian group with identity element as $\left\{ 0\right\}$, all elements of $\mathcal{U}$ are idempotent with respect to $\boxplus$, and the operation $\boxplus$ is isometric. It was conjectured that the size of any linear subspace code in $\mathbb{P}_q(n)$ can be at most $2^n$. In this work, we focus on different classes of linear subspace codes with a view to proving the conjectured upper bound for them as well as characterizing the maximal cases. We study connections of linear codes with lattices and a few combinatorial objects. Binary linear block codes and linear subspace codes are subspaces of a finite vector space over $\mathbb{F}_2$. We identify common features in their structures and prove analogous results for subspace codes including the Union-Intersection theorem. We investigate a class of linear subspace codes which are closed under intersection and show that these codes are equivalent to codes derived from a partition of a linearly independent set. The set of indecomposable codewords in a linear code closed under intersection is proved to generate the code. We verify the conjectured upper bound of $2^n$ for this class of linear codes and show that the maximal codes are essentially codes derived from a fixed basis. We prove linear codes that are sublattices of the projective lattice are precisely those closed under intersection. The sublattice is geometric distributive. We also give an alternate definition of codes derived from a fixed basis and prove that it is equivalent to the one presented in the existing literature. A code in a projective space is equidistant if the distance between each pair of distinct codewords are equal. A similarity in structure is established between equidistant linear subspace codes and $\lambda$-intersecting families, which are studied in the combinatorics of finite sets. We prove the conjectured bound for equidistant linear codes in $\mathbb{P}_2(n)$ and also determine the extremal case which is shown to be closely related to the Fano plane. Equidistant linear codes attaining maximum cardinality for all values of $n \ge 4$ are constructed. Such constructions are shown as $q$-analogs of a particular class of intersecting families called sunflowers. For positive integer values of $r$, construction of equidistant linear codes in $\mathbb{P}_q(n)$ is shown to be possible from any $(2^r - 1)$-subset of a Grassmannian $\mathcal{G}_q(n, 2k)$ with certain intersecting property. This proves constant distance decouples the translation invariance on the subspace distance metric for linear codes. We generalize linear subspace codes as $L$-intersecting families and give a construction for $|L| = 2$ that attains size $2^n$ with larger minimum distance than codes derived from a fixed basis. The conjectured upper bound is proved to hold for $L$-intersecting codes when $|L| = 2, q = 2$.

In this thesis, three problems have been considered and new coding schemes have been devised for each of them. The first is related to distributed function computation, the second to coding for distributed storage and the final problem is based on locally correctable codes. A common theme of the first two problems considered is distributed computation. The first problem is motivated by the problem of distributed function computation considered by Korner and Marton, where the goal is to compute XOR of two binary sources at the receiver. It has been shown that linear encoders give better sum rates for some source distributions as compared to the usual Slepian-Wolf scheme. We generalize this distributed function computation setting to the case of more than two sources and the receiver is interested in computing multiple linear combinations of the sources. Consider `m' random variables each of which takes values from a finite field and are associated with a certain joint probability distribution. The receiver is interested in the lossless computation of `s' linear combinations of the m random variables. By considering the set of all linear combinations of m random variables as a vector space V , this problem can be interpreted as a subspace-computation problem. For this problem, we develop three increasingly refined approaches, all based on linear encoders. The first two approaches which are termed as common code approach and selected subspace approach, use a common matrix to encode all the sources. In the common code approach, the desired subspace W is computed at the receiver, whereas in the selected subspace approach, possibly a larger subspace U which contains the desired subspace is computed. The larger subspace U which gives the minimum sum rate itself is based on a decomposition of vector space V into a chain of subspaces. The chain of subspaces is determined by the joint probability distribution of m random variables and a notion of normalized measure of entropy. The third approach is a nested code approach, where all the encoding matrices are nested and the same subspace U which is identified in the selected subspace approach is computed. We characterize the sum rates under all the three approaches. The sum rate under nested code approach is no larger than both selected subspace approach and Slepian-Wolf approach. For a large class of joint distributions and subspaces W , the nested code scheme is shown to improve upon Slepian-Wolf scheme. Additionally, a class of source distributions and subspaces are identified, for which the nested code approach is sum-rate optimal. In the second problem, we consider a distributed storage network, where data is stored across nodes in a network which are failure-prone. The goal is to store data reliably and efficiently. For a required level of reliability, it is of interest to minimise storage overhead and also of interest to perform node repair efficiently. Conventionally replication and maximum distance separable (MDS) codes are employed in such systems. Though replication is very efficient in terms of node repair, the storage overhead is high. MDS codes have low storage overhead but even the repair of a single failed node requires contacting a large number of nodes and downloading all their data. We consider two coding solutions that have recently been proposed, which enable efficient node repair in case of single node failure. The first solution called regenerating codes seeks to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. We extend these results in two directions. In the first one, we introduce the notion of codes with locality where the local codes have minimum distance more than 2 and hence can recover a code symbol locally even in the presence of multiple erasures. These codes are termed as codes with local erasure correction. We say that a code has information locality if there exists a set of message symbols, each of which is covered by local codes. A code is said to have all-symbol locality if all the code symbols are covered by local codes. An upper bound on the minimum distance of codes with information locality is presented and codes that are optimal with respect to this bound are constructed. We make a connection between codes with local erasure correction and concatenated codes. The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. There are two well known classes of regenerating codes known as minimum storage regenerating (MSR) codes and minimum bandwidth regenerating (MBR) codes. We derive two upper bounds on the minimum distance of vector-alphabet codes with locality, one for the case when the local codes are MSR codes and the second for the case when the local codes are MBR codes. We also provide several optimal constructions of both classes of codes which achieve their respective minimum distance bounds with equality. The third problem deals with locally correctable codes. A block code of length `n' is said to be locally correctable, if there exists a randomized algorithm such that any one of the coordinates of the codeword can be recovered by querying at most `r' coordinates, even in presence of some fraction of errors. We study the local correctability of linear codes whose duals contain 4-designs. We also derive a bound relating `r' and fraction of errors that can be tolerated, when each instance of the randomized algorithm is `t'-error correcting instead of simple parity computation.

In this thesis, three problems have been considered and new coding schemes have been devised for each of them. The first is related to distributed function computation, the second to coding for distributed storage and the final problem is based on locally correctable codes. A common theme of the first two problems considered is distributed computation. The first problem is motivated by the problem of distributed function computation considered by Korner and Marton, where the goal is to compute XOR of two binary sources at the receiver. It has been shown that linear encoders give better sum rates for some source distributions as compared to the usual Slepian-Wolf scheme. We generalize this distributed function computation setting to the case of more than two sources and the receiver is interested in computing multiple linear combinations of the sources. Consider `m' random variables each of which takes values from a finite field and are associated with a certain joint probability distribution. The receiver is interested in the lossless computation of `s' linear combinations of the m random variables. By considering the set of all linear combinations of m random variables as a vector space V , this problem can be interpreted as a subspace-computation problem. For this problem, we develop three increasingly refined approaches, all based on linear encoders. The first two approaches which are termed as common code approach and selected subspace approach, use a common matrix to encode all the sources. In the common code approach, the desired subspace W is computed at the receiver, whereas in the selected subspace approach, possibly a larger subspace U which contains the desired subspace is computed. The larger subspace U which gives the minimum sum rate itself is based on a decomposition of vector space V into a chain of subspaces. The chain of subspaces is determined by the joint probability distribution of m random variables and a notion of normalized measure of entropy. The third approach is a nested code approach, where all the encoding matrices are nested and the same subspace U which is identified in the selected subspace approach is computed. We characterize the sum rates under all the three approaches. The sum rate under nested code approach is no larger than both selected subspace approach and Slepian-Wolf approach. For a large class of joint distributions and subspaces W , the nested code scheme is shown to improve upon Slepian-Wolf scheme. Additionally, a class of source distributions and subspaces are identified, for which the nested code approach is sum-rate optimal. In the second problem, we consider a distributed storage network, where data is stored across nodes in a network which are failure-prone. The goal is to store data reliably and efficiently. For a required level of reliability, it is of interest to minimise storage overhead and also of interest to perform node repair efficiently. Conventionally replication and maximum distance separable (MDS) codes are employed in such systems. Though replication is very efficient in terms of node repair, the storage overhead is high. MDS codes have low storage overhead but even the repair of a single failed node requires contacting a large number of nodes and downloading all their data. We consider two coding solutions that have recently been proposed, which enable efficient node repair in case of single node failure. The first solution called regenerating codes seeks to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. We extend these results in two directions. In the first one, we introduce the notion of codes with locality where the local codes have minimum distance more than 2 and hence can recover a code symbol locally even in the presence of multiple erasures. These codes are termed as codes with local erasure correction. We say that a code has information locality if there exists a set of message symbols, each of which is covered by local codes. A code is said to have all-symbol locality if all the code symbols are covered by local codes. An upper bound on the minimum distance of codes with information locality is presented and codes that are optimal with respect to this bound are constructed. We make a connection between codes with local erasure correction and concatenated codes. The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. There are two well known classes of regenerating codes known as minimum storage regenerating (MSR) codes and minimum bandwidth regenerating (MBR) codes. We derive two upper bounds on the minimum distance of vector-alphabet codes with locality, one for the case when the local codes are MSR codes and the second for the case when the local codes are MBR codes. We also provide several optimal constructions of both classes of codes which achieve their respective minimum distance bounds with equality. The third problem deals with locally correctable codes. A block code of length `n' is said to be locally correctable, if there exists a randomized algorithm such that any one of the coordinates of the codeword can be recovered by querying at most `r' coordinates, even in presence of some fraction of errors. We study the local correctability of linear codes whose duals contain 4-designs. We also derive a bound relating `r' and fraction of errors that can be tolerated, when each instance of the randomized algorithm is `t'-error correcting instead of simple parity computation.

Large-Scale Subspace Clustering (LSSC) is an interesting and important problem in big data era. However, most existing methods (i.e., sparse or low-rank subspace clustering) cannot be directly used for solving LSSC because they suffer from the high time complexity-quadratic or cubic in n (the number of data points). To overcome this limitation, we propose a Fast Regression Coding (FRC) to optimize regression codes, and simultaneously train a non-linear function to approximate the codes. By using FRC, we develop an efficient Regression Coding Clustering (RCC) framework to solve the LSSC problem. It consists of sampling, FRC and clustering. RCC randomly samples a small number of data points, quickly calculates the codes of all data points by using the non-linear function learned from FRC, and employs a large-scale spectral clustering method to cluster the codes. Besides, we provide a theorem guarantee that the non-linear function has a first-order approximation ability and a group effect. The theorem manifests that the codes are easily used to construct a dividable similarity graph. Compared with the state-of-the-art LSSC methods, our model achieves better clustering results in large-scale datasets.

This research presents multiple strategies to improve the computation efficiency of solving combustion reaction kinetics. All strategies in this work are error-free compared to other methods based on result tabulation, dynamic mechanism reduction, and stiffness removal with quasi-equilibrium assumption and lower-dimensional manifold attraction. In the presented methods, the Jacobian matrix are solved by either direct linear solver or preconditioned Krylov subspace method. Different Jacobian matrix construction methods are designed with exploiting the characteristics of reaction network. The methods are systematically tested using reaction mechanisms of different size, and with different initial conditions. The performance of the presented methods are also compared with existing codes. The results shows that each specific method has higher performance for certain mechanisms. The reason for the performance differences are analyzed and a guideline for selecting method is provided. The presented methods are implemented into CFD code to efficiently simulate the reaction flow without dealing with the heterogeneity caused by dynamic mechanism reduction, quasi-equilibrium assumption, etc. It is also possible to combine the presented methods with problem-reducing methods to further optimize the reaction kinetics computation.

The color constancy hypothesis predicts that the color appearance associated with a vector of cone responses shifts as the visual system adjusts to changes in illumination. We measure color appearance using a classification paradigm1 and verify that changes in illumination do induce shifts in color appearance. Because there are many illuminant spectral power distributions, it is not possible to measure the shifts induced by all of them. If color constancy is to be a useful guide to the prediction of color appearance, the shift induced by any illuminant must be predicted by the shifts induced by a small set of illuminants. We show that when the set of surfaces encountered by the visual system is restricted, the filtering action of the cone spectral responsivities strongly limits the illuminant variation that can be detected at the level of the cone responses. The illuminant variations that are not filtered by the cones form a linear subspace. We test whether the shifts induced by illuminants in this subspace can be predicted from the shifts induced by each of the subspace’s basis illuminants.

The mussel trap is an important component used in nuclear power plant (NPP). The component belongs to RCC-P nuclear safety class 3, code and class RCC-M3, seismic category 1F and Q.A category Q2. The mussel trap is made up of screen, half-sphere, main flanges, nozzles, rotors, bolts, motor, supports and so on. The loads requirements in design conditions contain both internal loads and external loads. The loads have dead weight, pressure, nozzles loads and seismic loads. In this paper, the finite element model of the mussel trap is built with shell element using the structural analysis software-ANSYS. The stress analysis is based on linear elastic static analysis. The subspace iteration method is used for the modal analysis of the mussel trap. The static analysis is used for the mussel trap under deadweight, pressure and nozzle loads. At last, an evaluation of all loads combinations stresses against the respective stress limit for plate- and shell-type components and linear type systems is done according to the requirements of relative criteria specified in RCC-M. The evaluation result demonstrates that all loads combinations stresses of the mussel trap structure meet the requirements of RCC-M.

Designing phononic crystals by creating frequency bandgaps is of particular interest in the engineering of elastic and acoustic microstructured materials. Mathematically, the problem of optimizing the frequency bandgaps is often nonconvex, as it requires the maximization of the higher indexed eigenfrequency and the minimization of the lower indexed eigenfrequency. A novel algorithm [1] has been previously developed to reformulate the original nonlinear, nonconvex optimization problem to an iteration-specific semidefinite program (SDP). This algorithm separates two consecutive eigenvalues — effectively maximizing bandgap (or bandwidth) — by separating the gap between two orthogonal subspaces, which are comprised columnwise of “important” eigenvectors associated with the eigenvalues being bounded. By doing so, we avoid the need of computation of eigenvalue gradient by computing the gradient of affine matrices with respect to the decision variables. In this work, we propose an even more efficient algorithm based on linear programming (LP). The new formulation is obtained via approximation of the semidefinite cones by judiciously chosen linear bases, coupled with “delayed constraint generation”. We apply the two convex conic formulations, namely, the semidefinite program and the linear program, to solve the bandgap optimization problems. By comparing the two methods, we demonstrate the efficacy and efficiency of the LP-based algorithm in solving the category of eigenvalue bandgap optimization problems.