Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

Formation of Pb(Ti,Zr)O3, from thermal decomposition of oxalate precursors

Lead zir conyl oxalate hexahydrate (LZO) and lead titanyl zirconyl oxalate hydrate (LTZO) are prepared and characterized. Their thermal decompositions have been investigated by thermoanalytical and gas analysis techniques. The decomposition in air or oxygen has three steps — dehydration, decomposition of the oxalate to a carbonate and the decomposition of carbonate to PbZrO3. In non oxidising atmosphere, partial reduction of Pb(II) to Pb(0) takes place at the oxalate decomposition step. The formation of free metallic lead affects the stoichiometry of the intermediate carbonate and yields a mixture of Pb(Ti,Zr)O3 and ZrO2 as the final products. By maintaining oxidising atmosphere and low heating rate, direct preparation of stoichiometric, crystalline Pb(Ti,Zr)O3 at 550°C is possible from the corresponding oxalate precursor.

Thermodynamic Properties and Phase Diagram for the System MoO2–TiO2

The activity of molybdenum dioxide (MoO2) in the MoO2–TiO2 solid solutions was measured at 1600 K using a solid-state cell incorporating yttria-doped thoria as the electrolyte. For two compositions, the emf was also measured as a function of temperature. The cell was designed such that the emf is directly related to the activity of MoO2 in the solid solution. The results show monotonic variation of activity with composition, suggesting a complete range of solid solutions between the end members and the occurrence of MoO2 with a tetragonal structure at 1600 K. A large positive deviation from Raoult's law was found. Excess Gibbs energy of mixing is an asymmetric function of composition and can be represented by the subregular solution model of Hardy as follows.The temperature dependence of the emf for two compositions is reasonably consistent with ideal entropy of mixing. A miscibility gap is indicated at a lower temperature with the critical point characterized by Tc (K)=1560 and . Recent studies indicate that MoO2 undergoes a transition from a monoclinic to tetragonal structure at 1533 K with a transition entropy of 9.91 J·(mol·K)−1. The solid solubility of TiO2 with rutile structure in MoO2 with a monoclinic structure is negligible. These features give rise to a eutectoid reaction at 1412 K. The topology of the computed phase diagram differs significantly from that suggested by Pejryd.

Kinetics of propellant decomposition

Equations for solid-state decompositions which are controlled by the phase-boundary movement and nucleation have been examined using ammonium perchlorate/polystyrene propellant decomposition at 503 K and 533 K. It was found that 3 different equations governed by the nucleation process show a good fit of data at these temperatures. However, the best fit was obtained for the following Avrami-Erofeev equation, [-In (1 - α]1/4=kt.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Accelerating frequency-domain diffuse optical tomographic image reconstruction using graphics processing units

Diffuse optical tomographic image reconstruction uses advanced numerical models that are computationally costly to be implemented in the real time. The graphics processing units (GPUs) offer desktop massive parallelization that can accelerate these computations. An open-source GPU-accelerated linear algebra library package is used to compute the most intensive matrix-matrix calculations and matrix decompositions that are used in solving the system of linear equations. These open-source functions were integrated into the existing frequency-domain diffuse optical image reconstruction algorithms to evaluate the acceleration capability of the GPUs (NVIDIA Tesla C 1060) with increasing reconstruction problem sizes. These studies indicate that single precision computations are sufficient for diffuse optical tomographic image reconstruction. The acceleration per iteration can be up to 40, using GPUs compared to traditional CPUs in case of three-dimensional reconstruction, where the reconstruction problem is more underdetermined, making the GPUs more attractive in the clinical settings. The current limitation of these GPUs in the available onboard memory (4 GB) that restricts the reconstruction of a large set of optical parameters, more than 13, 377. (C) 2010 Society of Photo-Optical Instrumentation Engineers. DOI: 10.1117/1.3506216]

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.

Plate-shaped transformation products in zirconium-base alloys

Plate-shaped products resulting from martensitic, diffusional, and mixed mode transformations in zirconium-base alloys are compared. in the present study. These alloys are particularly suitable for the comparison in view of the fact that the lattice correspondence between the parent beta (bcc) and the product alpha (hcp) or gamma-hydride (fct) phases are remarkably similar for different types of transformations. Crystallographic features such as orientation relations, habit planes, and interface structures associated with these transformations have been compared:, with a view toward examining whether the transformation mechanisms have characteristic imprints on these experimental observables. Martensites exhibiting dislocated lath, internally twinned plate, and self-accommodating three-plate cluster morphologies have been encountered in Zr-2.5Nb alloy. Habit planes corresponding to all these morphologies have been found to be consistent with the predictions based on the invariant plane strain (IFS) criterion. Different morphologies have been found to reflect the manner in which the neighboring martensite variants are assembled. Lattice-invariant shears (LISs) for all these cases have been identified to be either {10 (1) over bar 1}(alpha) ((1) over bar 123)(alpha) slip or twinning on (10 (1) over bar 1)(alpha) planes. Widmanstatten alpha precipitates, forming in a step-quenching treatment, have been shown to have a lath morphology, the alpha/beta interface being decorated with a periodic array of (c + a) dislocations at a spacing of 8 to 10 nm. The line vectors of these dislocations are nearly parallel to the invariant lines. The alpha precipitates, forming in the retained beta phase on aging, exhibit an internally twinned structure with a zigzag habit plane. Average habit planes for the morphologies have been found to lie near the {103}(beta) - {113}(beta) poles, which are close to the specific variant of the {112}(beta) plane, which transforms into a prismatic plane of the type {1 (1) over bar 00}(alpha). The crystallography of the formation of the gamma-hydride phase (fct) from both the alpha and beta phases is seen to match the IFS predictions. While the beta-gamma transformation can be treated approximately as a simple shear on the basal plane involving a change in the stacking sequence, the alpha-gamma transformation call be conceptually broken into a alpha --> beta transformation following the Burgers correspondence and the simple beta-gamma shear process. The active eutectoid decomposition in the Zr-Cu system, beta --> alpha + beta', has been described in terms of cooperative growth of the alpha phase from the beta phase through the Burgers correspondence and of the partially ordered beta' (structurally similar to the equilibrium Zr2Cu phase) through an ordering process. Similarities and differences in crystallographic features of these transformations have been discussed. and the importance of the invariant line vector in deciding the geometry of the corresponding habit planes has been pointed out.

Experimental study of phase equilibria in the system Cu-Al-Sn

Phase equilibria in the Cu-rich corner of the ternary system Cu-Al-Sn have been re-investigated. Final equilibrium microstructures of 20 ternary alloy compositions near Cu3Al were used to refine the ternary phase diagram. The microstructures were characterized using optical microscopy (OM), x-ray diffraction (XRD), electron probe microanalysis and transmission electron microscopy. Isothermal sections at 853, 845, 833, 818, 808, 803 and 773 K have been composed. Vertical sections have been drawn at 2 and 3 at% Sn, showing beta(1) as a stable phase. Three-phase fields (alpha + beta + beta(1)) and (beta + beta(1) + gamma(1)) result from beta -> alpha + beta(1) eutectoid and beta + gamma(1) -> beta(1) peritectoid reactions forming metastable beta(1) in the binary Cu-Al. With the lowering of temperature from 853 to 818 K, these three-phase fields are shifted to lower Sn concentrations, with simultaneous shrinkage and shifting of (beta + beta(1)) two-phase field. The three-phase field (alpha + beta + gamma(1)) resulting from the binary reaction beta -> alpha + gamma(1) shifts to higher Sn contents, with associated shrinkage of the beta field, with decreasing temperature. With further reduction of temperature, a new ternary invariant reaction beta + beta(1) -> alpha + gamma(1) is observed at similar to 813 K. The beta disappears completely at 803 K, giving rise to the three-phase field (alpha + beta(1) + gamma(1)). Some general guidelines on the role of ternary additions (M) on the stability of the ordered beta(1) phase are obtained by comparing the results of this study with data in the literature on other systems in the systems group Cu-Al-M.

Quantum simulation using fidelity-profile optimization

Experimental quantum simulation of a Hamiltonian H requires unitary operator decomposition (UOD) of its evolution unitary U = exp(-iHt) in terms of native unitary operators of the experimental system. Here, using a genetic algorithm, we numerically evaluate the most generic UOD (valid over a continuous range of Hamiltonian parameters) of the unitary operator U, termed fidelity-profile optimization. The optimization is obtained by systematically evaluating the functional dependence of experimental unitary operators (such as single-qubit rotations and time-evolution unitaries of the system interactions) to the Hamiltonian (H) parameters. Using this technique, we have solved the experimental unitary decomposition of a controlled-phase gate (for any phase value), the evolution unitary of the Heisenberg XY interaction, and simulation of the Dzyaloshinskii-Moriya (DM) interaction in the presence of the Heisenberg XY interaction. Using these decompositions, we studied the entanglement dynamics of a Bell state in the DM interaction and experimentally verified the entanglement preservation procedure of Hou et al. Ann. Phys. (N.Y.) 327, 292 (2012)] in a nuclear magnetic resonance quantum information processor.

Approximation of Spatio-Temporal Random Processes Using Tensor Decomposition

A new representation of spatio-temporal random processes is proposed in this work. In practical applications, such processes are used to model velocity fields, temperature distributions, response of vibrating systems, to name a few. Finding an efficient representation for any random process leads to encapsulation of information which makes it more convenient for a practical implementations, for instance, in a computational mechanics problem. For a single-parameter process such as spatial or temporal process, the eigenvalue decomposition of the covariance matrix leads to the well-known Karhunen-Loeve (KL) decomposition. However, for multiparameter processes such as a spatio-temporal process, the covariance function itself can be defined in multiple ways. Here the process is assumed to be measured at a finite set of spatial locations and a finite number of time instants. Then the spatial covariance matrix at different time instants are considered to define the covariance of the process. This set of square, symmetric, positive semi-definite matrices is then represented as a third-order tensor. A suitable decomposition of this tensor can identify the dominant components of the process, and these components are then used to define a closed-form representation of the process. The procedure is analogous to the KL decomposition for a single-parameter process, however, the decompositions and interpretations vary significantly. The tensor decompositions are successfully applied on (i) a heat conduction problem, (ii) a vibration problem, and (iii) a covariance function taken from the literature that was fitted to model a measured wind velocity data. It is observed that the proposed representation provides an efficient approximation to some processes. Furthermore, a comparison with KL decomposition showed that the proposed method is computationally cheaper than the KL, both in terms of computer memory and execution time.

Wind speed prediction using spatio-temporal covariance

High wind poses a number of hazards in different areas such as structural safety, aviation, and wind energy-where low wind speed is also a concern, pollutant transport, to name a few. Therefore, usage of a good prediction tool for wind speed is necessary in these areas. Like many other natural processes, behavior of wind is also associated with considerable uncertainties stemming from different sources. Therefore, to develop a reliable prediction tool for wind speed, these uncertainties should be taken into account. In this work, we propose a probabilistic framework for prediction of wind speed from measured spatio-temporal data. The framework is based on decompositions of spatio-temporal covariance and simulation using these decompositions. A novel simulation method based on a tensor decomposition is used here in this context. The proposed framework is composed of a set of four modules, and the modules have flexibility to accommodate further modifications. This framework is applied on measured data on wind speed in Ireland. Both short-and long-term predictions are addressed.

Optimal values of bipartite entanglement in a tripartite system

For a general tripartite system in some pure state, an observer possessing any two parts will see them in a mixed state. By the consequence of Hughston-Jozsa-Wootters theorem, each basis set of local measurement on the third part will correspond to a particular decomposition of the bipartite mixed state into a weighted sum of pure states. It is possible to associate an average bipartite entanglement ((S) over bar) with each of these decompositions. The maximum value of (S) over bar is called the entanglement of assistance (E-A) while the minimum value is called the entanglement of formation (E-F). An appropriate choice of the basis set of local measurement will correspond to an optimal value of (S) over bar; we find here a generic optimality condition for the choice of the basis set. In the present context, we analyze the tripartite states W and GHZ and show how they are fundamentally different. (C) 2014 Elsevier B.V. All rights reserved.

Effect of processing route on phase stability in equiatomic multicomponent Ti20Fe20Ni20Co20Cu20 high entropy alloy

The evolution of microstructure and phase formation in equiatomic Ti20Fe20Ni20Co20Cu20 high entropy alloy synthesised by conventional arc melting followed with suction casting and ball milling with spark plasma sintering route is distinctly different. The cast microstructure exhibits one body centre cubic and two face centre cubic high entropy phases based on titanium, cobalt and copper respectively along with a eutectic containing Ti2Ni type Laves phase. On the contrary, spinodal decomposed microstructure consisting of cobalt and copper solid solution is obtained in the sintered sample. However, long term annealing of cast sample at 950 degrees C reveals a eutectoid transformation with different phases than the cast sample. The aforementioned observations are discussed using CALPHAD thermodynamical approach and available literature.

Medidas alternativas de la pobreza en el Gran Buenos Aires, 1995-2006

Resumen: En este trabajo, calculamos y analizamos el Índice de Severidad de la pobreza o squared poverty gap para el Gran Buenos Aires, en el período 1995-2006. Este índice es una de las tres medidas más conocidas correspondientes a la clase FGT (Foster, Greer and Thorbecke 1984), aunque menos utilizada que la incidencia o head count ratio (calculado por el INDEC), y la brecha de pobreza o poverty gap. El Índice de Severidad de la pobreza tiene en cuenta no sólo la distancia que separa a los pobres de la línea de pobreza (como en el caso de la brecha de pobreza) sino también la desigualdad entre los pobres. Es decir, le da un mayor peso a los hogares que están más alejados de la línea de pobreza. Por lo tanto, este índice cumple con el axioma de transferencia, a diferencia de los otros dos. Calculamos el Índice de Severidad tanto a nivel hogares como individuos. Además, realizamos una descomposición del índice por grupos – según la situación laboral, el nivel de educación, el tamaño del hogar, la edad y el sexo del jefe de hogar; y calculamos el riesgo relativo de cada grupo. Realizamos también una comparación entre los índices de incidencia (INDEC) y severidad. Concluimos presentando los índices de incidencia y severidad para todo el país, y su descomposición por regiones, para el año 2006.