摘要 :
For many multi-dimensional data applications, tensor operations as well as relational operations both need to be supported throughout the data lifecycle. Tensor based representations (including two widely used tensor decomposition...
展开
For many multi-dimensional data applications, tensor operations as well as relational operations both need to be supported throughout the data lifecycle. Tensor based representations (including two widely used tensor decompositions, CP and Tucker decompositions) are proven to be effective in multiaspect data analysis and tensor decomposition is an important tool for capturing high-order structures in multi-dimensional data. Although tensor decomposition is shown to be effective for multi-dimensional data analysis, the cost of tensor decomposition is often very high. Since the number of modes of the tensor data is one of the main factors contributing to the costs of the tensor operations, in this paper, we focus on reducing the modality of the input tensors to tackle the computational cost of the tensor decomposition process. We propose a novel decomposition-by-normalization scheme that first normalizes the given relation into smaller tensors based on the functional dependencies of the relation, decomposes these smaller tensors, and then recombines the sub-results to obtain the overall decomposition. The decomposition and recombination steps of the decomposition-by-normalization scheme fit naturally in settings with multiple cores. This leads to a highly efficient, effective, and parallelized decomposition-by-normalization algorithm for both dense and sparse tensors for CP and Tucker decompositions. Experimental results confirm the efficiency and effectiveness of the proposed decomposition-by-normalization scheme compared to the conventional nonnegative CP decomposition and Tucker decomposition approaches.
收起
摘要 :
Matrix decompositions are used for many data mining purposes. One of these purposes is to find a concise but interpretable representation of a given data matrix. Different decomposition formulations have been proposed for this tas...
展开
Matrix decompositions are used for many data mining purposes. One of these purposes is to find a concise but interpretable representation of a given data matrix. Different decomposition formulations have been proposed for this task, many of which assume a certain property of the input data ( e. g., nonnegativity) and aim at preserving that property in the decomposition. In this paper we propose new decomposition formulations for binary matrices, namely the Boolean CX and CUR decompositions. They are natural combinations of two previously presented decomposition formulations. We consider also two subproblems of these decompositions and present a rigorous theoretical study of the subproblems. We give algorithms for the decompositions and for the subproblems, and study their performance via extensive experimental evaluation. We show that even simple algorithms can give accurate and intuitive decompositions of real data, thus demonstrating the power and usefulness of the proposed decompositions.
收起
摘要 :
In the early 1980s, Cunningham described a unique decomposition of a strongly-connected graph. A linear time bound for finding it in the special case of an undirected graph has been given previously, but up until now, the best bou...
展开
In the early 1980s, Cunningham described a unique decomposition of a strongly-connected graph. A linear time bound for finding it in the special case of an undirected graph has been given previously, but up until now, the best bound known for the general case has been O(n(3)). We give an O(m log n) bound.
收起
摘要 :
A graph G is a common multiple of two graphs H-1 and H-2 if G is both H-1-decomposable and H-2-decomposable. In this paper, we consider the case where H-1 is the path of length k Pk+1 and H-2 is the star with 1 edges S-1. We deter...
展开
A graph G is a common multiple of two graphs H-1 and H-2 if G is both H-1-decomposable and H-2-decomposable. In this paper, we consider the case where H-1 is the path of length k Pk+1 and H-2 is the star with 1 edges S-1. We determine, for all positive integers k and 1, the set of integers q for which there exists a common multiple of Pk+1 and S-1 having precisely q edges.
收起
摘要 :
Recent theories of morphological processing have been dominated by thenotion that morphologically complex words are decomposed into theirconstituents on the basis of their semantic properties. In this article we arguethat the weig...
展开
Recent theories of morphological processing have been dominated by thenotion that morphologically complex words are decomposed into theirconstituents on the basis of their semantic properties. In this article we arguethat the weight of evidence now suggests that the recognition of morpholo-gically complex words begins with a rapid morphemic segmentation basedsolely on the analysis of orthography. Following a review of this evidence, wediscuss the characteristics of this form of decomposition, speculate on what itspurpose might be, consider how it might be learned in the developing reader,and describe what is known of its neural bases. Our discussion ends byreflecting on how evidence for semantically based decomposition might be(re)interpreted in the context of the orthographically based form of decom-position that we have described.
收起
摘要 :
We derive a CUR-type factorization for tensors in the Tucker format based on inter-polatory decomposition, which we will denote as higher order interpolatory Decomposition (HOID). Given a tensor X, the algorithm provides a set of ...
展开
We derive a CUR-type factorization for tensors in the Tucker format based on inter-polatory decomposition, which we will denote as higher order interpolatory Decomposition (HOID). Given a tensor X, the algorithm provides a set of column vectors {C-n}(n)(d)=1 which are columns extracted from the mode-n tensor unfolding, along with a core tensor g and, together, they satisfy some error bounds. Compared to the higher order SVD algorithm, the HOID provides a decomposition that preserves certain important features of the original tensor such as sparsity, non-negativity, integer values, etc. Error bounds along with detailed estimates of computational costs are provided. The algorithms proposed in this paper have been validated against carefully chosen numerical examples which highlight the favorable properties of the algorithms. Related methods for subset selection proposed for matrix CUR decomposition, such as the discrete empirical interpolation method and leverage score sampling, have also been extended to tensors and are compared against our proposed algorithms.
收起
摘要 :
Peat humification or decomposition is a frequently used proxy to extract past time changes in hydrology and climate from peat bogs. During the past century several methods to determine changes in peat decomposition have been intro...
展开
Peat humification or decomposition is a frequently used proxy to extract past time changes in hydrology and climate from peat bogs. During the past century several methods to determine changes in peat decomposition have been introduced. Most of these methods are operationally defined only and the chemical changes underlying the decomposition process are often poorly understood and lack validation. Owing to the chemically undefined nature of many humification analyses the comparison of results obtained by different methods is difficult. In this study we compared changes in peat decomposition proxies in cores of two peat bogs (K?nigsmoor, KK; Kleines Rotes Bruch, KRB) from the Harz Mountains (Germany) using C/N ratios, Fourier transform infrared spectra absorption (FTIR) intensities, Rock Eval~? oxygen and hydrogen indices, δ~(13)C and δ~(15)N isotopic signatures and UV-absorption (UV-ABS) of NaOH peat extracts. In order to explain parallels and discrepancies between these methods, one of the cores was additionally analysed by pyrolysis gas chromatography mass spectrometry (pyrolysis-GC-MS). Pyrolysis-GC-MS data provide detailed information on a molecular level, which allows differentiation of both changes attributed to decomposition processes and changes in vegetation. Principal component analysis was used to identify and separate the effects of changes in vegetation pattern and decomposition processes because both may occur simultaneously upon changes in bog hydrology. Records of decomposition proxies show similar historical development at both sites, indicating external forcing such as climate as controlling the process. All decomposition proxies except UV-ABS and δ~(15)N isotopes show similar patterns in their records and reflect to different extents signals of decomposition. The molecular composition of the KK core reveals that these changes are mainly attributed to decomposition processes and to a lesser extent to changes in vegetation. Changes in the molecular composition indicate that peat decomposition in the KK bog is mainly characterized by preferential decomposition of phenols and polysaccharides and relative enrichment of aliphatics during drier periods. Enrichment of lignin and other aromatics during decomposition was also observed but showed less variation than polysaccharides or aliphatics, and presumably reflects changes in vegetation associated with changes in hydrology of the bogs. Significant correlations with polysaccharide and aliphatic pyrolysis products were found for C/N ratios, FTIR-band intensities and for hydrogen index values, supporting that these decomposition indices provide reasonable information. Correlations of polysaccharide and aliphatic pyrolysis products with oxygen index values and δ~(13)C was weaker, assumingly indicating carboxylation of the peat during drier periods and enrichment of isotopically lighter peat components during decomposition, respectively. FTIR, C/N ratio, pyrolysis- GC-MS analyses and Rock Eval hydrogen indices appear to reflect mass loss and related changes in the molecular peat composition during mineralization best. Pyrolysis-GC-MS allows disentangling the decomposition processes and vegetation changes. UV-ABS measurements of alkaline peat extracts show only weak correlation with other decomposition proxies and pyrolysis results as they mainly reflect the formation of humic acids through humification and to a lesser extent mass loss during mineralization.
收起
摘要 :
Semiquinones are persistent free environmental radicals formed as important initial products from the decomposition of dihydroxylated benzene isomers. This study develops detailed decomposition pathways for the thermal decompositi...
展开
Semiquinones are persistent free environmental radicals formed as important initial products from the decomposition of dihydroxylated benzene isomers. This study develops detailed decomposition pathways for the thermal decomposition of the three isomeric semiquinone radicals. Branching ratios based on the calculated high-pressure limit reaction rate constants predict that p-benzoquinone is a major product from the unimolecular decomposition of the p-semiquinone radical, while the formation of o-benzoquinone from the o-semiquinone radical corresponds to a minor channel. This finding is consistent with the absence of o-benzoquinone from the thermal degradation of the 1,2-dihydroxybenzene isomer and the abundance of p-benzoquinone from the thermal decomposition of 1,4-dihydroxybenzene. Ring contraction/CO elimination is shown to be the dominant sink pathway for the o-semiquinone and m-semiquinone radicals. Thermochemical properties, in terms of enthalpies of formation, entropies, and heat capacities for dihydroxylated benzene isomers, semiquinone radicals, and benzoquinones, are evaluated by quantum chemical calculations. Values of the enthalpies of formation calculated by the B3LYP/GTLarge method show good agreement with those obtained at the G3B3 level of theory.
收起
摘要 :
Let (V, T) be a 3-fold triple system and (V, C) a 4-fold 4-cycle system on the same set V. This choice of indices 3 and 4 ensures that each system contains the same number of cycles: |T| = |C|. We pair up the cycles, {t, c}, where...
展开
Let (V, T) be a 3-fold triple system and (V, C) a 4-fold 4-cycle system on the same set V. This choice of indices 3 and 4 ensures that each system contains the same number of cycles: |T| = |C|. We pair up the cycles, {t, c}, where t ∈ T and c ∈ C, in such a way that t and c share one edge. If t = (x, y, z) and c = (x, y, u, v), so t and c share the edge {x, y}, then we retain the 5-cycle (z, x, v, u, y) and remove the repeated edge {x, y}. Doing this for all the pairs {t, c} , we rearrange all the shared edges, common to t and c, into further 5-cycles, so that the result is a 7-fold 5-cycle system on V. The necessary conditions are that the order |V| is 1 or 5 (mod 10); these conditions are shown to be sufficient for such a "metamorphosis" from pairs of 3- and 4-cycles into 5-cycles.
收起
摘要 :
One studies the structure of 2D symmetric fourth-order tensors, i.e. having both minor and major indicial symmetries. Verchery polar decomposition is rewritten in a tensorial form entitled Tensorial Polar Decomposition. The main r...
展开
One studies the structure of 2D symmetric fourth-order tensors, i.e. having both minor and major indicial symmetries. Verchery polar decomposition is rewritten in a tensorial form entitled Tensorial Polar Decomposition. The main result is that any 2D symmetric fourth-order tensor can be written in terms of second-order tensors only in a decomposition that makes explicitly appear invariants and symmetry classes. The link with harmonic decomposition is made thanks to Kelvin decomposition of its harmonic term. (C) 2015 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.
收起
原文获取