Narrow Results

We analyze the parallel performance of randomized interpolative decomposition by decomposing low rank complex-valued Gaussian random matrices of about 100 GB. We chose a Cray XMT supercomputer as it provides an almost ideal PRAM model permitting quick investigation of parallel algorithms without obfuscation from hardware idiosyncrasies. We obtain that on non-square matrices performance scales almost linearly with runtime about 100 times faster on 128 processors. We also verify that numerically discovered error bounds still hold on matrices two orders of magnitude larger than those previously tested.

The significance of community structure in complex networks, such as social, biological, and online networks, has been widely recognized. Detecting communities in social media networks typically relies on two sources of information: the network’s topological structure and node attributes. Incorporating rich node content attribute information poses both flexibility and challenges for community detection. Traditional approaches either focus on mining one information source or linearly combining results from both sources, which fails to effectively fuse the information. This paper introduces a practical collaborative learning approach that explores the multi-dimensional attribute characteristics of nodes to facilitate community division. By leveraging graphical matrix decomposition, the proposed algorithm, CDGMF, improves the effectiveness and robustness of community detection. Experimental results demonstrate the method’s ability to effectively utilize node attribute information for guiding community detection, resulting in higher-quality community divisions.

Production equipment is crucial to efficiency enhancement and product quality in the manufacturing industry. Repairman and removable standbys can be configured to support continuous production in order to minimize downtime and capacity loss associated with the malfunctioning of manufacturing equipment. Under these conditions, an idle repairman temporarily leaving the system to perform other tasks can undermine service performance. This paper presents a limited-capacity machine repair problem with standbys, two failure modes, and a working vacation policy. The steady-state system-size distribution is derived via the matrix analysis method and matrix decomposition. Based on steady-state probabilities, we derived closed-form formulations of several critical metrics for the assessment of system characteristics. Sensitivity analysis is performed to illustrate the effects of uncertainty in system parameters. Management implications are also addressed.

We introduce a new zero-sum matrix game for modeling search in structured domains. In this game, one player tries to find a "bug" while the other tries to hide it. Both players exploit the structure of the "search" domain. Intuitively, this search game is a mathematical generalization of the well known binary search. The generalization is from searching over totally ordered sets to searching over more complex search domains such as trees, partial orders and general set systems. As there must be one row for every search strategy, and there are exponentially many ways to search even in very simple search domains, the game's matrix has exponential size ("space"). In this work we present two ways to reduce the space required to compute the Nash value (in pure strategies) of this game:

• First we show that a Nash equilibrium in pure strategies can be computed by using a backward induction on the matrices of each "part" or sub structure of the search domain. This can significantly reduce the space required to represent the game.

• Next, we show when general search domains can be represented as DAGs (Directed Acycliqe Graphs). As a result, the Nash equilibrium can be directly computed using the DAG. Consequently the space needed to compute the desired search strategy is reduced to O(n²) where n is the size of the search domain.

This study focuses on heavy-tailed noise reduction in multivariate signals, with no knowledge of their forms. We propose a non-parametric multivariate denoising technique which is robust to heavy-tailed noise. Using a univariate robust linear regression, we construct a multivariate non-parametric method. We design a robust matrix decomposition and, consequently, propose a robust procedure including this new decomposition. In addition, we develop a robust procedure for the imputation of the missing points of the signals. The key advantage of our methods over the previous tools is the robustness to the heavy-tailed observations. The results of our simulation study confirm the good performance of the proposed methods.

Let $R$ be a local ring with maximal ideal $𝔪$, let $n$ be a natural number greater than $1$ and let $A=(a_{ij})$ be a matrix in the general linear group ${\mathrm{\text{GL}}}_n(R)$ of degree $n$ over $R$. We firstly show that if the matrix $(\overline{a_{ij}})$ is nonscalar in ${\mathrm{\text{GL}}}_n(R/𝔪)$ and $s_1,s_2,\dots ,s_{n-1}$ are invertible elements in $R$, then there exists an invertible element $s_n\in R$ such that $A$ is similar to the product $VU$ in which $V$ is a lower uni-triangular matrix and $U$ is an upper triangular matrix whose diagonal entries are $s_1,s_2,\dots ,s_n$. We then present some applications of this factorization to find decompositions of matrices in ${\mathrm{\text{GL}}}_n(R)$ into product of commutators and involutions.

Multi-view feature selection is an important research direction in the field of multi-view learning. To remove the negative effect of irrelevant and redundant information and select the important features from the multi-view data, in this paper, we propose a novel hierarchical unsupervised multi-view feature selection method, which integrates matrix decomposition and hierarchical regularization as a joint model. Specifically, to exploit the consistency information of multiple views for projection matrix, we project the multiple views into a latent basis space based on a matrix decomposition model. The hierarchical regularization containing the $l_{2,1}$-norm, dependence and Frobenius-norm is imposed on projection matrix to, respectively, exploit the row-level, dependency-level and view-level feature selection. We also develop an efficient optimization algorithm to optimize our method. Extensive experimental results on six popular multi-view datasets show the effectiveness and superiority of our method by comparing with the state-of-the-art methods.

Non-negative matrix factorization (NMF) has proven to be a useful decomposition technique for multivariate data, where the non-negativity constraint is necessary to have a meaningful physical interpretation. NMF reduces the dimensionality of non-negative data by decomposing it into two smaller non-negative factors with physical interpretation for class discovery. The NMF algorithm, however, assumes a deterministic framework. In particular, the effect of the data noise on the stability of the factorization and the convergence of the algorithm are unknown. Collected data, on the other hand, is stochastic in nature due to measurement noise and sometimes inherent variability in the physical process. This paper presents new theoretical and applied developments to the problem of non-negative matrix factorization (NMF). First, we generalize the deterministic NMF algorithm to include a general class of update rules that converges towards an optimal non-negative factorization. Second, we extend the NMF framework to the probabilistic case (PNMF). We show that the Maximum a posteriori (MAP) estimate of the non-negative factors is the solution to a weighted regularized non-negative matrix factorization problem. We subsequently derive update rules that converge towards an optimal solution. Third, we apply the PNMF to cluster and classify DNA microarrays data. The proposed PNMF is shown to outperform the deterministic NMF and the sparse NMF algorithms in clustering stability and classification accuracy.

A recurrence scheme is presented to decompose an n-qubit unitary gate to the product of no more than N(N - 1)/2 single qubit gates with small number of controls, where N = 2ⁿ. Detailed description of the recurrence steps and formulas for the number of k-controlled single qubit gates in the decomposition are given. Comparison of the result to a previous scheme is presented, and future research directions are discussed.

The low accuracy near the boundary or the interface in SPH method has been paid extensive attention. The Finite Particle Method (FPM) is a significant improvement to the traditional SPH method, which can greatly improve the computational accuracy for boundary particles. However, there are still some inherent defects for FPM, such as the long computing time and the potential numerical instability. By conducting matrix decomposition on the basic equations of FPM, an improved FPM method (IFPM) is proposed, which can not only maintain the high accuracy of FPM for boundary particles, but also keep the invertibility of the coefficient matrix in FPM. The numerical results show that the IFPM is really an effective improvement to traditional FPM, which could greatly reduce the computing time. Finally, the modified method is applied to two transient problems.

As an implementation form of basis function, interpolation matrices (IMs) have a crucial impact on parametric level set method (PLSM)-based structural topology optimization (STO). However, there are few studies on compressing IM into triangular matrix (TM) with less storage and computation. Algorithm using LU decomposition and Algorithm using innovative asymmetric basis functions that transform the IMs of compactly supported radial basis functions (CSRBFs) into highly sparse TMs are proposed. Theoretical derivation and numerical experiments show that they effectively improve computational efficiency.

The subgroups XU(2), YU(2), and ZU(2) of the unitary group U(2) allow to find twenty-four different decompositions of an arbitrary $2\times 2$ unitary matrix. Because the group YU(2) has not been considered before, 20 out of the 24 decompositions are new. Introducing this YU(2) group allows to highlight, within quantum circuit design, a symmetry similar to the threefold symmetry of the Pauli matrices of spin systems. Similar subgroups of the unitary group U($n$) lead to various new decompositions of an arbitrary $n\times n$ unitary matrix. Whereas for $n$ equal 2, this leads to the synthesis of single-qubit quantum gates, for $n$ equal a power of 2, this leads to new design methods for multiple-qubit circuits.