In this dissertation, we introduce and analyse a scheme for the fast evaluation of integrals stemming from boundary element methods including discretisations of the classical single and double layer potential operators. Our method is based on the parametrisation of boundary elements in terms of a d-dimensional parameter tuple. We interpret the integral as a real-valued function f depending on d parameters and show that f is smooth in a d-dimensional box. A standard interpolation of f by polynomials leads to a d-dimensional tensor which is given by the values of f at the interpolation points. This tensor may be approximated in a low rank tensor format like the canonical format or the hierarchical format. The tensor approximation has to be done only once and allows us to evaluate interpolants in O(dr(m+1)) operations in the canonical format, or O(dk³ + dk(m + 1)) operations in the hierarchical format, where m denotes the interpolation order and the ranks r, k are small integers. In particular, we apply an efficient black box scheme in the hierarchical tensor format in order to adaptively approximate tensors even in high dimensions d with a prescribed (but heuristic) target accuracy. By means of detailed numerical experiments, we demonstrate that highly accurate integral values can be obtained at very moderate costs.

This thesis consists of 4 major parts. In the first part (Chapters 1-2), we introduce the overview, motivation, and contribution of our works, and extensively survey the current literature for 6 related topics. In the second part (Chapters 3-7), we explore the concept of "Self-Similarity" in two challenging scenarios, namely, the Action Recognition and the Motion Retrieval. We build three-dimensional volume representations for both scenarios, and devise effective techniques that can produce compact representations encoding the internal dynamics of data. In the third part (Chapter 8), we explore the challenging action spotting problem, and propose a feature-independent unsupervised framework that is effective in spotting action under various real situations, even under heavily perturbed conditions. The final part (Chapters 9) is dedicated to conclusions and future works. For action recognition, we introduce a generic method that does not depend on one particular type of input feature vector. We make three main contributions: (i) We introduce the concept of Joint Self-Similarity Volume (Joint SSV) for modeling dynamical systems, and show that by using a new optimized rank-1 tensor approximation of Joint SSV one can obtain compact low-dimensional descriptors that very accurately preserve the dynamics of the original system, e.g. an action video sequence; (ii) The descriptor vectors derived from the optimized rank-1 approximation make it possible to recognize actions without explicitly aligning the action sequences of varying speed of execution or difference frame rates; (iii) The method is generic and can be applied using different low-level features such as silhouettes, histogram of oriented gradients (HOG), etc. Hence, it does not necessarily require explicit tracking of features in the space-time volume. Our experimental results on five public datasets demonstrate that our method produces very good results and outperforms many baseline methods. For action recognition for incomplete videos, we determine whether incomplete videos that are often discarded carry useful information for action recognition, and if so, how one can represent such mixed collection of video data (complete versus incomplete, and labeled versus unlabeled) in a unified manner. We propose a novel framework to handle incomplete videos in action classification, and make three main contributions: (i) We cast the action classification problem for a mixture of complete and incomplete data as a semi-supervised learning problem of labeled and unlabeled data. (ii) We introduce a two-step approach to convert the input mixed data into a uniform compact representation. (iii) Exhaustively scrutinizing 280 configurations, we experimentally show on our two created benchmarks that, even when the videos are extremely sparse and incomplete, it is still possible to recover useful information from them, and classify unknown actions by a graph based semi-supervised learning framework. For motion retrieval, we present a framework that allows for a flexible and an efficient retrieval of motion capture data in huge databases. The method first converts an action sequence into a self-similarity matrix (SSM), which is based on the notion of self-similarity. This conversion of the motion sequences into compact and low-rank subspace representations greatly reduces the spatiotemporal dimensionality of the sequences. The SSMs are then used to construct order-3 tensors, and we propose a low-rank decomposition scheme that allows for converting the motion sequence volumes into compact lower dimensional representations, without losing the nonlinear dynamics of the motion manifold. Thus, unlike existing linear dimensionality reduction methods that distort the motion manifold and lose very critical and discriminative components, the proposed method performs well, even when inter-class differences are small or intra-class differences are large. In addition, the method allows for an efficient retrieval and does not require the time-alignment of the motion sequences. We evaluate the performance of our retrieval framework on the CMU mocap dataset under two experimental settings, both demonstrating very good retrieval rates. For action spotting, our framework does not depend on any specific feature (e.g. HOG/HOF, STIP, silhouette, bag-of-words, etc.), and requires no human localization, segmentation, or framewise tracking. This is achieved by treating the problem holistically as that of extracting the internal dynamics of video cuboids by modeling them in their natural form as multilinear tensors. To extract their internal dynamics, we devised a novel Two-Phase Decomposition (TP-Decomp) of a tensor that generates very compact and discriminative representations that are robust to even heavily perturbed data. Technically, a Rank-based Tensor Core Pyramid (Rank-TCP) descriptor is generated by combining multiple tensor cores under multiple ranks, allowing to represent video cuboids in a hierarchical tensor pyramid. The problem then reduces to a template matching problem, which is solved efficiently by using two boosting strategies: (i) to reduce the search space, we filter the dense trajectory cloud extracted from the target video; (ii) to boost the matching speed, we perform matching in an iterative coarse-to-fine manner. Experiments on 5 benchmarks show that our method outperforms current state-of-the-art under various challenging conditions. We also created a challenging dataset called Heavily Perturbed Video Arrays (HPVA) to validate the robustness of our framework under heavily perturbed situations.

No description available.

No description available.

In this thesis the application of novel tensor decomposition and tensor representation techniques in highly accurate post Hartree-Fock methods is evaluated. These representation techniques can help to overcome the steep scaling behaviour of high level ab-initio calculations with increasing system size and therefore break the "curse of dimensionality". After a comparison of various tensor formats the application of the "canonical polyadic" format (CP) is described in detail. There, especially the casting of a normal, index based tensor into the CP format (tensor decomposition) and a method for a low rank approximation (rank reduction) of the two-electron integrals in the AO basis are investigated. The decisive quantity for the applicability of the CP format is the scaling of the rank with increasing system and basis set size. The memory requirements and the computational effort for tensor manipulations in the CP format are only linear in the number of dimensions but still depend on the expansion length (rank) of the approximation. Furthermore, the AO-MO transformation and a MP2 algorithm with decomposed tensors in the CP format is evaluated and the scaling with increasing system and basis set size is investigated. Finally, a Coupled-Cluster algorithm based only on low-rank CP representation of the MO integrals is developed. There, especially the successive tensor contraction during the iterative solution of the amplitude equations and the error propagation upon multiple application of the reduction procedure are discussed. In conclusion the overall complexity of a Coupled-Cluster procedure with tensors in CP format is evaluated and some possibilities for improvements of the rank reduction procedure tailored to the needs in electronic structure calculations are shown. / Die vorliegende Arbeit beschäftigt sich mit der Anwendung neuartiger Tensorzerlegungs- und Tensorrepesentationstechniken in hochgenauen post Hartree-Fock Methoden um das hohe Skalierungsverhalten dieser Verfahren mit steigender Systemgröße zu verringern und somit den "Fluch der Dimensionen" zu brechen. Nach einer vergleichenden Betrachtung verschiedener Representationsformate wird auf die Anwendung des "canonical polyadic" Formates (CP) detailliert eingegangen. Dabei stehen zunächst die Umwandlung eines normalen, indexbasierten Tensors in das CP Format (Tensorzerlegung) und eine Methode der Niedrigrang Approximation (Rangreduktion) für Zweielektronenintegrale in der AO Basis im Vordergrund. Die entscheidende Größe für die Anwendbarkeit ist dabei das Skalierungsverhalten das Ranges mit steigender System- und Basissatzgröße, da der Speicheraufwand und die Berechnungskosten für Tensormanipulationen im CP Format zwar nur noch linear von der Anzahl der Dimensionen des Tensors abhängen, allerdings auch mit der Expansionslänge (Rang) skalieren. Im Anschluss wird die AO-MO Transformation und der MP2 Algorithmus mit zerlegten Tensoren im CP Format diskutiert und erneut das Skalierungsverhalten mit steigender System- und Basissatzgröße untersucht. Abschließend wird ein Coupled-Cluster Algorithmus vorgestellt, welcher ausschließlich mit Tensoren in einer Niedrigrang CP Darstellung arbeitet. Dabei wird vor allem auf die sukzessive Tensorkontraktion während der iterativen Bestimmung der Amplituden eingegangen und die Fehlerfortpanzung durch Anwendung des Rangreduktions-Algorithmus analysiert. Abschließend wird die Komplexität des gesamten Verfahrens bewertet und Verbesserungsmöglichkeiten der Reduktionsprozedur aufgezeigt.

In this dissertation, we introduce and analyse a scheme for the fast evaluation of integrals stemming from boundary element methods including discretisations of the classical single and double layer potential operators. Our method is based on the parametrisation of boundary elements in terms of a d-dimensional parameter tuple. We interpret the integral as a real-valued function f depending on d parameters and show that f is smooth in a d-dimensional box. A standard interpolation of f by polynomials leads to a d-dimensional tensor which is given by the values of f at the interpolation points. This tensor may be approximated in a low rank tensor format like the canonical format or the hierarchical format. The tensor approximation has to be done only once and allows us to evaluate interpolants in O(dr(m+1)) operations in the canonical format, or O(dk³ + dk(m + 1)) operations in the hierarchical format, where m denotes the interpolation order and the ranks r, k are small integers. In particular, we apply an efficient black box scheme in the hierarchical tensor format in order to adaptively approximate tensors even in high dimensions d with a prescribed (but heuristic) target accuracy. By means of detailed numerical experiments, we demonstrate that highly accurate integral values can be obtained at very moderate costs.

In der vorliegenden Arbeit wird ein neues Tensorformat vorgestellt und eingehend analysiert. Das hierarchische Format verwendet einen binären Baum, um den Tensorraum der Ordnung d mit einer geschachtelten Unterraumstruktur zu versehen. Der Speicheraufwand für diese Darstellung ist von der Größenordnung O(dnr + dr^3), wobei n den Speicheraufwand in den Ansatzräumen kennzeichnet und r ein Rangparameter ist, der durch die Dimensionen der geschachtelten Unterräume bestimmt wird. Das hierarchische Format umfasst verschiedene Standardformate zur Tensordarstellung wie das kanonische oder r-Term-Format und die Unterraum-/Tucker-Darstellung. Die in dieser Arbeit entwickelte zugehörige Arithmetik inklusive mehrerer Approximationsmethoden basiert auf stabilen Methoden der Linearen Algebra, insbesondere die Singulärwertzerlegung und die QR-Zerlegung sind von zentraler Bedeutung. Die rechnerische Komplexität ist hierbei O(dnr^2+dr^4). Die lineare Abhängigkeit von der Ordnung d des Tensorraumes ist hervorzuheben. Für die verschiedenen Approximationsmethoden, deren Effizienz und Effektivität für die Anwendbarkeit des neuen Formates entscheidend sind, werden qualitative und quantitative Fehlerabschätzungen gezeigt. Umfassende numerische Experimente mit einem Fokus auf den Approximationsmethoden bestätigen zum einen die theoretischen Resultate und belegen die Stärken der neuen Tensordarstellung, zeigen aber zum anderen auch weitere, eher überraschende positive Eigenschaften der mit FastHOSVD bezeichneten schnellsten Kürzungsmethode. / In this dissertation we present and a new format for the representation of tensors and analyse its properties. The hierarchical format uses a binary tree in order to define a hierarchical structure of nested subspaces in the tensor space of order d. The strorage requirements are O(dnr+dr^3) where n is determined by the storage requirements in the ansatz spaces and r is a rank parameter determined by the dimensions of the nested subspaces. The hierarchichal representation contains the standard representation like canonical or r-term representation and subspace or Tucker representation. The arithmetical operations that have been developed in this work, including several approximation methods, are based on stable Linear Alebra methods, especially the singular value decomposition (SVD) and the QR decomposition are of importance. The computational complexity is O(dnr^2+dr^4). The linear dependence from the order d of the tensor space is important. The approximation methods are one of the key ingredients for the applicability of the new format and we present qualitative and quantitative error estimates. Numerical experiments approve the theoretical results and show some additional, but unexpected positive aspects of the fastest method called FastHOSVD.

In der vorliegenden Arbeit wird ein neues Tensorformat vorgestellt und eingehend analysiert. Das hierarchische Format verwendet einen binären Baum, um den Tensorraum der Ordnung d mit einer geschachtelten Unterraumstruktur zu versehen. Der Speicheraufwand für diese Darstellung ist von der Größenordnung O(dnr + dr^3), wobei n den Speicheraufwand in den Ansatzräumen kennzeichnet und r ein Rangparameter ist, der durch die Dimensionen der geschachtelten Unterräume bestimmt wird. Das hierarchische Format umfasst verschiedene Standardformate zur Tensordarstellung wie das kanonische oder r-Term-Format und die Unterraum-/Tucker-Darstellung. Die in dieser Arbeit entwickelte zugehörige Arithmetik inklusive mehrerer Approximationsmethoden basiert auf stabilen Methoden der Linearen Algebra, insbesondere die Singulärwertzerlegung und die QR-Zerlegung sind von zentraler Bedeutung. Die rechnerische Komplexität ist hierbei O(dnr^2+dr^4). Die lineare Abhängigkeit von der Ordnung d des Tensorraumes ist hervorzuheben. Für die verschiedenen Approximationsmethoden, deren Effizienz und Effektivität für die Anwendbarkeit des neuen Formates entscheidend sind, werden qualitative und quantitative Fehlerabschätzungen gezeigt. Umfassende numerische Experimente mit einem Fokus auf den Approximationsmethoden bestätigen zum einen die theoretischen Resultate und belegen die Stärken der neuen Tensordarstellung, zeigen aber zum anderen auch weitere, eher überraschende positive Eigenschaften der mit FastHOSVD bezeichneten schnellsten Kürzungsmethode. / In this dissertation we present and a new format for the representation of tensors and analyse its properties. The hierarchical format uses a binary tree in order to define a hierarchical structure of nested subspaces in the tensor space of order d. The strorage requirements are O(dnr+dr^3) where n is determined by the storage requirements in the ansatz spaces and r is a rank parameter determined by the dimensions of the nested subspaces. The hierarchichal representation contains the standard representation like canonical or r-term representation and subspace or Tucker representation. The arithmetical operations that have been developed in this work, including several approximation methods, are based on stable Linear Alebra methods, especially the singular value decomposition (SVD) and the QR decomposition are of importance. The computational complexity is O(dnr^2+dr^4). The linear dependence from the order d of the tensor space is important. The approximation methods are one of the key ingredients for the applicability of the new format and we present qualitative and quantitative error estimates. Numerical experiments approve the theoretical results and show some additional, but unexpected positive aspects of the fastest method called FastHOSVD.

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors. The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is \[ \min_{\rank(X) = k} \det (B - X A)(B - X A)\tp, \] where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix. Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations. The remaining two papers discuss computational methods for the best multilinear rank approximation problem \[ \min_{\cB} \| \cA - \cB\| \] where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product \[ \cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu}, \] where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.

In this thesis the application of novel tensor decomposition and tensor representation techniques in highly accurate post Hartree-Fock methods is evaluated. These representation techniques can help to overcome the steep scaling behaviour of high level ab-initio calculations with increasing system size and therefore break the "curse of dimensionality". After a comparison of various tensor formats the application of the "canonical polyadic" format (CP) is described in detail. There, especially the casting of a normal, index based tensor into the CP format (tensor decomposition) and a method for a low rank approximation (rank reduction) of the two-electron integrals in the AO basis are investigated. The decisive quantity for the applicability of the CP format is the scaling of the rank with increasing system and basis set size. The memory requirements and the computational effort for tensor manipulations in the CP format are only linear in the number of dimensions but still depend on the expansion length (rank) of the approximation. Furthermore, the AO-MO transformation and a MP2 algorithm with decomposed tensors in the CP format is evaluated and the scaling with increasing system and basis set size is investigated. Finally, a Coupled-Cluster algorithm based only on low-rank CP representation of the MO integrals is developed. There, especially the successive tensor contraction during the iterative solution of the amplitude equations and the error propagation upon multiple application of the reduction procedure are discussed. In conclusion the overall complexity of a Coupled-Cluster procedure with tensors in CP format is evaluated and some possibilities for improvements of the rank reduction procedure tailored to the needs in electronic structure calculations are shown. / Die vorliegende Arbeit beschäftigt sich mit der Anwendung neuartiger Tensorzerlegungs- und Tensorrepesentationstechniken in hochgenauen post Hartree-Fock Methoden um das hohe Skalierungsverhalten dieser Verfahren mit steigender Systemgröße zu verringern und somit den "Fluch der Dimensionen" zu brechen. Nach einer vergleichenden Betrachtung verschiedener Representationsformate wird auf die Anwendung des "canonical polyadic" Formates (CP) detailliert eingegangen. Dabei stehen zunächst die Umwandlung eines normalen, indexbasierten Tensors in das CP Format (Tensorzerlegung) und eine Methode der Niedrigrang Approximation (Rangreduktion) für Zweielektronenintegrale in der AO Basis im Vordergrund. Die entscheidende Größe für die Anwendbarkeit ist dabei das Skalierungsverhalten das Ranges mit steigender System- und Basissatzgröße, da der Speicheraufwand und die Berechnungskosten für Tensormanipulationen im CP Format zwar nur noch linear von der Anzahl der Dimensionen des Tensors abhängen, allerdings auch mit der Expansionslänge (Rang) skalieren. Im Anschluss wird die AO-MO Transformation und der MP2 Algorithmus mit zerlegten Tensoren im CP Format diskutiert und erneut das Skalierungsverhalten mit steigender System- und Basissatzgröße untersucht. Abschließend wird ein Coupled-Cluster Algorithmus vorgestellt, welcher ausschließlich mit Tensoren in einer Niedrigrang CP Darstellung arbeitet. Dabei wird vor allem auf die sukzessive Tensorkontraktion während der iterativen Bestimmung der Amplituden eingegangen und die Fehlerfortpanzung durch Anwendung des Rangreduktions-Algorithmus analysiert. Abschließend wird die Komplexität des gesamten Verfahrens bewertet und Verbesserungsmöglichkeiten der Reduktionsprozedur aufgezeigt.