A Tensor Approximation Approach to Dimensionality Reduction

Dimensionality reduction has recently been extensively studied for computer vision applications. We present a novel multilinear algebra based approach to reduced dimensionality representation of multidimensional data, such as image ensembles, video sequences and volume data. Before reducing the dimensionality we do not convert it into a vector as is done by traditional dimensionality reduction techniques like PCA. Our approach works directly on the multidimensional form of the data (matrix in 2D and tensor in higher dimensions) to yield what we call a Datum-as-Is representation. This helps exploit spatio-temporal redundancies with less information loss than image-as-vector methods. An efficient rank-R tensor approximation algorithm is presented to approximate higher-order tensors. We show that rank-R tensor approximation using Datum-as-Is representation generalizes many existing approaches that use image-as-matrix representation, such as generalized low rank approximation of matrices (GLRAM) (Ye, Y. in Mach. Learn. 61:167–191, 2005), rank-one decomposition of matrices (RODM) (Shashua, A., Levin, A. in CVPR’01: Proceedings of the 2001 IEEE computer society conference on computer vision and pattern recognition, p. 42, 2001) and rank-one decomposition of tensors (RODT) (Wang, H., Ahuja, N. in ICPR ’04: ICPR ’04: Proceedings of the 17th international conference on pattern recognition (ICPR’04), vol. 1, pp. 44–47, 2004). Our approach yields the most compact data representation among all known image-as-matrix methods. In addition, we propose another rank-R tensor approximation algorithm based on slice projection of third-order tensors, which needs fewer iterations for convergence for the important special case of 2D image ensembles, e.g., video. We evaluated the performance of our approach vs. other approaches on a number of datasets with the following two main results. First, for a fixed compression ratio, the proposed algorithm yields the best representation of image ensembles visually as well as in the least squares sense. Second, proposed representation gives the best performance for object classification. A shorter version of this paper was published at IEEE CVPR 2005 (Wang and Ahuja 2005).     

A General BRDF Representation Based on Tensor Decomposition

Generating photo‐realistic images through Monte Carlo rendering requires efficient representation of light–surface interaction and techniques for importance sampling. Various models with good representation abilities have been developed but only a few of them have their importance sampling procedure. In this paper, we propose a method which provides a good bidirectional reflectance distribution function (BRDF) representation and efficient importance sampling procedure. Our method is based on representing BRDF as a function of tensor products. Four‐dimensional measured BRDF tensor data are factorized using Tucker decomposition. A large data set is used for comparing the proposed BRDF model with a number of well‐known BRDF models. It is shown that the underlying model provides good approximation to BRDFs.     

An effective format for representing graphic information

An intelligent format of the compressed graphic data representation, based on correlation-extremal recognition methods is described in this work. Corresponding fields of a new data representation structure are formed by compression, recognition, masking, and coding methods for describing data in the format of the linear-contour model obtained by vectoring initial images of graphic documents. The theoretical reasoning for the efficiency of the graphic data representation in the proposed format is given, which is demonstrated by examples in comparison with the most known formats.     

A new Steiner patch based file format for Additive Manufacturing processes

Additive Manufacturing (AM) processes adopt a layering approach for building parts in continuous slices and use the Standard Tessellation Language (STL) file format as an input to generate the slices during part manufacturing. However, the current STL format uses planar triangular facets to approximate the surfaces of the parts. This approximation introduces errors in the part representation which leads to additional errors downstream in the parts produced by AM processes. Recently, another file format called Additive Manufacturing File (AMF) was introduced by ASTM which seeks to use curved triangles based on second degree Hermite curves. However, while generating the slices for manufacturing the part, the curved triangles are recursively sub-divided back to planar triangles which may lead to the same approximation error present in the STL file. This paper introduces a new file format which uses curved Steiner patches instead of planar triangles for not only approximating the part surfaces but also for generating the slices. Steiner patches are bounded Roman surfaces and can be parametrically represented by rational Bezier equations. Since Steiner surfaces are of higher order, this new Steiner file format will have a better accuracy than the traditional STL and AMF formats and will lead to lower Geometric Dimensioning and Tolerancing (GD&T) errors in parts manufactured by AM processes. Since the intersection of a plane and the Steiner patch is a closed form mathematical solution, the slicing of the Steiner format can be accomplished with very little computational complexity. The Steiner representation has been used to approximate the surfaces of two test parts and the chordal errors in the surfaces are calculated. The chordal errors in the Steiner format are compared with the STL and AMF formats of the test surfaces and the results have been presented. Further, an error based adaptive tessellation algorithm is developed for generating the Steiner representation which reduces the number of curved facets while still improving the accuracy of the Steiner format. The test parts are virtually manufactured using the adaptive Steiner, STL and AMF format representations and the GD&T errors of the manufactured parts are calculated and compared. The results demonstrate that the modified Steiner format is able to significantly reduce the chordal and profile errors as compared to the STL and AMF formats.     

On tensor approximation of Green iterations for Kohn-Sham equations

In the present paper we discuss efficient rank-structured tensor approximation methods for 3D integral transforms representing the Green iterations for the Kohn-Sham equation. We analyse the local convergence of the Newton iteration to solve the Green’s function integral formulation of the Kohn-Sham model in electronic structure calculations. We prove the low-separation rank approximations for the arising discrete convolving kernels given by the Coulomb and Yukawa potentials 1/|x|, and e ^?λ|x|/|x|, respectively, with $x \in {\mathbb{R}}^{d} $ . Complexity analysis of the nonlinear iteration with truncation to the fixed Kronecker tensor-product format is presented. Our method has linear scaling in the univariate problem size. Numerical illustrations demostrate uniform exponential convergence of tensor approximations in the orthogonal Tucker and canonical formats.     

Curvature-Driven PDE Methods for Matrix-Valued Images

Matrix-valued data sets arise in a number of applications including diffusion tensor magnetic resonance imaging (DT-MRI) and physical measurements of anisotropic behaviour. Consequently, there arises the need to filter and segment such tensor fields. In order to detect edge-like structures in tensor fields, we first generalise Di Zenzo’s concept of a structure tensor for vector-valued images to tensor-valued data. This structure tensor allows us to extend scalar-valued mean curvature motion and self-snakes to the tensor setting. We present both two-dimensional and three-dimensional formulations, and we prove that these filters maintain positive semidefiniteness if the initial matrix data are positive semidefinite. We give an interpretation of tensorial mean curvature motion as a process for which the corresponding curve evolution of each generalised level line is the gradient descent of its total length. Moreover, we propose a geodesic active contour model for segmenting tensor fields and interpret it as a minimiser of a suitable energy functional with a metric induced by the tensor image. Since tensorial active contours incorporate information from all channels, they give a contour representation that is highly robust under noise. Experiments on three-dimensional DT-MRI data and an indefinite tensor field from fluid dynamics show that the proposed methods inherit the essential properties of their scalar-valued counterparts.     

Synthesizing efficient out-of-core programs for block recursivealgorithms using block-cyclic data distributions

In this paper, we present a framework for synthesizing I/O efficient out-of-core programs for block recursive algorithms, such as the fast Fourier transform (FFT) and block matrix transposition algorithms. Our framework uses an algebraic representation which is based on tensor products and other matrix operations. The programs are optimized for the striped Vitter and Shriver's two-level memory model in which data can be distributed using various cyclic(B) distributions in contrast to the normally used physical track distribution cyclic(B_d ), where B_d is the physical disk block size. We first introduce tensor bases to capture the semantics of block-cyclic data distributions of out-of-core data and also data access patterns to out-of-core data. We then present program generation techniques for tensor products and matrix transposition. We accurately represent the number of parallel I/O operations required for the synthesized programs for tensor products and matrix transposition as a function of tensor bases and data distributions. We introduce an algorithm to determine the data distribution which optimizes the performance of the synthesized programs. Further, we formalize the procedure of synthesizing efficient out-of-core programs for tensor product formulas with various block-cyclic distributions as a dynamic programming problem. We demonstrate the effectiveness of our approach through several examples. We show that the choice of an appropriate data distribution can reduce the number of passes to access out-of-core data by as large as eight times for a tensor product and the dynamic programming approach can largely reduce the number of passes to access out-of-core data for the overall tensor product formulas     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

Hierarchical tensor approximation of multi-dimensional visual data

Visual data comprise of multi-scale and inhomogeneous signals. In this paper, we exploit these characteristics and develop a compact data representation technique based on a hierarchical tensor-based transformation. In this technique, an original multi-dimensional dataset is transformed into a hierarchy of signals to expose its multi-scale structures. The signal at each level of the hierarchy is further divided into a number of smaller tensors to expose its spatially inhomogeneous structures. These smaller tensors are further transformed and pruned using a tensor approximation technique. Our hierarchical tensor approximation supports progressive transmission and partial decompression. Experimental results indicate that our technique can achieve higher compression ratios and quality than previous methods, including wavelet transforms, wavelet packet transforms, and single-level tensor approximation. We have successfully applied our technique to multiple tasks involving multi-dimensional visual data, including medical and scientific data visualization, data-driven rendering and texture synthesis.     

Adaptive Recompression of -Matrices for BEM

The efficient treatment of dense matrices arising, e.g., from the finite element discretisation of integral operators requires special compression techniques. In this article, we use a hierarchical low-rank approximation, the so-called -matrix, that approximates the dense stiffness matrix in admissible blocks (corresponding to subdomains where the underlying kernel function is smooth) by low rank matrices. The low rank matrices are assembled by the ACA+ algorithm, an improved variant of the well-known ACA method. We present an algorithm that can determine a coarser block structure that minimises the storage requirements (enhanced compression) and speeds up the arithmetic (e.g., inversion) in the -matrix format. This coarse approximation is done adaptively and on-the-fly to a given accuracy such that the matrix is assembled with minimal storage requirements while keeping the desired approximation quality. The benefits of this new recompression technique are demonstrated by numerical examples.     

Derivation of Glue Code for Agent Interoperation

Getting agents to communicate requires translating the data structures of the sender (the source representation) to the format required by the receiver (the target representation). Assuming that there is a formal theory of the semantics of the two formats, which explains both their meanings in terms of a neutral topic domain, we can cast the translation problem as solving higher-order functional equations. Some simple rules and strategies apparently suffice to solve these equations automatically. The strategies may be summarized as: decompose complex expressions, replacing topic-domain expressions with source-domain expressions when necessary. A crucial issue is getting the required formal theories of the source and target domains. We believe it is sufficient to find partial formalizations that grow as necessary.     

Optimizing the execution of XSLT stylesheets for querying transformed XML data

We have to deal with different data formats whenever data formats evolve or data must be integrated from heterogeneous systems. These data when implemented in XML for data exchange cannot be shared freely among applications without data transformation. A common approach to solve this problem is to convert the entire XML data from their source format to the applications’ target formats using the transformations rules specified in XSLT stylesheets. However, in many cases, not all XML data are required to be transformed except for a smaller part described by a user’s query (application). In this paper, we present an approach that optimizes the execution time of an XSLT stylesheet for answering a given XPath query by modifying the XSLT stylesheet in such a way that it would (a) capture only the parts in the XML data that are relevant to the query and (b) process only those XSLT instructions that are relevant to the query. We prove the correctness of our optimization approach, analyze its complexity and present experimental results. The experimental results show that our approach performs the best in terms of execution time, especially when many cost-intensive XSLT instructions can be excluded in the XSLT stylesheet.     

Manipulating algebraic specifications with term-based and graph-based representations

In an environment of continuous and rapid evolution, software design methodologies must incorporate techniques and tools that support changes in software artifacts. In the project, we are developing a tool targeted at software designers that integrates a collection of operations on algebraic specifications written in the language. The scope of includes not only modification of existing specifications, but also creation or derivation of new specifications, as well as their proof and execution, which are realized through inter-operability with existing tools. As involves the manipulation of software specification and inter-operability with other tools, the question of choosing appropriate representation formats is important. In this paper, we discuss the advantages and limitations of as a manipulation and exchange format in the setting of . We also present a new, graph-like format, which offers complementary features to a term-based format. Moreover, we present visualization utilities for these formats.     

An optimal storage format for sparse matrices

The irregular nature of sparse matrix-vector multiplication, Ax=y, has led to the development of a variety of compressed storage formats, which are widely used because they do not store any unnecessary elements. One of these methods, the Jagged Diagonal Storage format (JDS) is, in addition, considered appropriate for the implementation of iterative methods on parallel and vector processors. In this work we present the Transpose Jagged Diagonal Storage format (TJDS) which drew inspiration from the Jagged Diagonal Storage scheme but requires less storage space than JDS. We propose an alternative storage scheme which makes no assumptions about the sparsity pattern of the matrix and only needs three linear arrays instead of the four linear arrays required by JDS. Specifically, the data is aligned in such a way that the permutation array used in JDS, to permute the solution vector back to the original ordering, is unnecessary. This allow us to save the memory space required to store an integer vector of length n, where n stands for the number of columns in the sparse matrix A. This storage saving reaches, for the selection of matrices used in this work, from 14% up to 45% of the number of non-zero values of the sparse matrices. We present a case study of a 6×6 sparse matrix to show the data structures and the algorithm to compute Ax=y using the TJDS format.     

Ternary Sparse Matrix Representation for Volumetric Mesh Subdivision and Processing on GPUs

In this paper, we present a novel volumetric mesh representation suited for parallel computing on modern GPU architectures. The data structure is based on a compact, ternary sparse matrix storage of boundary operators. Boundary operators correspond to the first‐order top‐down relations of k‐faces to their (k ? 1)‐face facets. The compact, ternary matrix storage format is based on compressed sparse row matrices with signed indices and allows for efficient parallel computation of indirect and bottom‐up relations. This representation is then used in the implementation of several parallel volumetric mesh algorithms including Laplacian smoothing and volumetric Catmull‐Clark subdivision. We compare these algorithms with their counterparts based on OpenVolumeMesh and achieve speedups from 3× to 531×, for sufficiently large meshes, while reducing memory consumption by up to 36%.     

Riemann Surfaces, Plane Algebraic Curves and Their Period Matrices

The aim of this paper is to present theoretical basis for computing a representation of a compact Riemann surface as an algebraic plane curve and to compute a numerical approximation for its period matrix. We will describe a program C ars (Semmler et al., 1996) that can be used to define Riemann surfaces for computations. C ars allows one also to perform the Fenchel–Nielsen twist and other deformations on Riemann surfaces.Almost all theoretical results presented here are well known in classical complex analysis and algebraic geometry. The contribution of the present paper is the design of an algorithm which is based on the classical results and computes first an approximation of a polynomial representing a given compact Riemann surface as a plane algebraic curve and further computes an approximation for a period matrix of this curve. This algorithm thus solves an important problem in the general case. This problem was first solved, in the case of symmetric Riemann surfaces, in Seppälä (1994).     

Methods and software tools to support combined binary code analysis

Methods and tools for binary code analysis developed in the Institute of System Programming, Russian Academy of Sciences, and their applications in algorithm and data format recovery are considered. The executable code of various general-purpose CPU architectures is analyzed. The analysis is performed given no source codes, debugging information, and specific OS version requirements. The approach implies collecting a detailed machine instruction level execution trace; a method for successively increasing presentation level; extraction of algorithm’s code followed by structuring of both code and data formats it processes. Important results are obtained, viz. an intermediate representation is developed that allows carrying out most preliminary processing tasks and algorithm code extraction without having to focus on specifics of a given machine; and a method and software tool are developed for automated recovery of network message and file formats. The tools are integrated into the unified analysis platform that supports their combined use. The architecture behind the platform is also described. Examples of its application to real programs are given.     

Ellipsoidal techniques for reachability analysis: internal approximation

For the reach tube of a linear time-varying system with ellipsoidal bounds on the control variable consider the following approximation problem. Find a tight ellipsoid-valued tube inside the reach tube that touches it along any prespecified smooth curve on the boundary. We construct this ellipsoidal tube, and show that if the given curve is itself a system trajectory, the tube can be calculated recursively, with minimum computational burden.