Fast algorithms for singular value decomposition and the inverse of nearly low-rank matrices.
Ontology highlight
ABSTRACT:
SUBMITTER: Xu C
PROVIDER: S-EPMC10246826 | biostudies-literature | 2023 Jun
REPOSITORIES: biostudies-literature
Publications
Fast algorithms for singular value decomposition and the inverse of nearly low-rank matrices.
Xu Chen C Xu Weiwei W Jing Kaili K
National science review 20230325 6
This perspective focuses on the fast algorithm design for singular value decomposition and inverse computation of nearly low-rank matrices that are potentially of big sizes. ...[more]
Similar Datasets
Project description:Multi-channel phased receive arrays have been widely adopted for magnetic resonance imaging (MRI) and spectroscopy (MRS). An important step in the use of receive arrays for MRS is the combination of spectra collected from individual coil channels. The goal of this work was to implement an improved strategy termed OpTIMUS (i.e., optimized truncation to integrate multi-channel MRS data using rank-R singular value decomposition) for combining data from individual channels. OpTIMUS relies on spectral windowing coupled with a rank-R decomposition to calculate the optimal coil channel weights. MRS data acquired from a brain spectroscopy phantom and 11 healthy volunteers were first processed using a whitening transformation to remove correlated noise. Whitened spectra were then iteratively windowed or truncated, followed by a rank-R singular value decomposition (SVD) to empirically determine the coil channel weights. Spectra combined using the vendor-supplied method, signal/noise2 weighting, previously reported whitened SVD (rank-1), and OpTIMUS were evaluated using the signal-to-noise ratio (SNR). Significant increases in SNR ranging from 6% to 33% (P ≤ 0.05) were observed for brain MRS data combined with OpTIMUS compared with the three other combination algorithms. The assumption that a rank-1 SVD maximizes SNR was tested empirically, and a higher rank-R decomposition, combined with spectral windowing prior to SVD, resulted in increased SNR.
| S-EPMC7317403 | biostudies-literature
Project description:We present a simple and effective method for combining distance matrices from multiple genes on identical taxon sets to obtain a single representative distance matrix from which to derive a combined-gene phylogenetic tree. The method applies singular value decomposition (SVD) to extract the greatest common signal present in the distances obtained from each gene. The first right eigenvector of the SVD, which corresponds to a weighted average of the distance matrices of all genes, can thus be used to derive a representative tree from multiple genes. We apply our method to three well known data sets and estimate the uncertainty using bootstrap methods. Our results show that this method works well for these three data sets and that the uncertainty in these estimates is small. A simulation study is conducted to compare the performance of our method with several other distance based approaches (namely SDM, SDM* and ACS97), and we find the performances of all these approaches are comparable in the consensus setting. The computational complexity of our method is similar to that of SDM. Besides constructing a representative tree from multiple genes, we also demonstrate how the subsequent eigenvalues and eigenvectors may be used to identify if there are conflicting signals in the data and which genes might be influential or outliers for the estimated combined-gene tree.
| S-EPMC3986248 | biostudies-literature
Project description:MotivationHigh throughput biomedical measurements normally capture multiple overlaid biologically relevant signals and often also signals representing different types of technical artefacts like e.g. batch effects. Signal identification and decomposition are accordingly main objectives in statistical biomedical modeling and data analysis. Existing methods, aimed at signal reconstruction and deconvolution, in general, are either supervised, contain parameters that need to be estimated or present other types of ad hoc features. We here introduce SubMatrix Selection Singular Value Decomposition (SMSSVD), a parameter-free unsupervised signal decomposition and dimension reduction method, designed to reduce noise, adaptively for each low-rank-signal in a given data matrix, and represent the signals in the data in a way that enable unbiased exploratory analysis and reconstruction of multiple overlaid signals, including identifying groups of variables that drive different signals.ResultsThe SMSSVD method produces a denoised signal decomposition from a given data matrix. It also guarantees orthogonality between signal components in a straightforward manner and it is designed to make automation possible. We illustrate SMSSVD by applying it to several real and synthetic datasets and compare its performance to golden standard methods like PCA (Principal Component Analysis) and SPC (Sparse Principal Components, using Lasso constraints). The SMSSVD is computationally efficient and despite being a parameter-free method, in general, outperforms existing statistical learning methods.Availability and implementationA Julia implementation of SMSSVD is openly available on GitHub (https://github.com/rasmushenningsson/SubMatrixSelectionSVD.jl).Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC6361234 | biostudies-literature
Project description:The characterization of organic compounds in polluted matrices by eco-friendly three-dimensional (3D) fluorescence spectroscopy coupled with chemometric algorithms constitutes a powerful alternative to the separation techniques conventionally used. However, the systematic presence of Rayleigh and Raman scattering signals in the excitation-emission matrices (EEMs) complicates the spectral decomposition via PARAllel FACtor analysis (PARAFAC) due to the nontrilinear structure of these signals. Likewise, the specific problem of selectivity in spectroscopy for unexpected chemical components in a complex sample may render its chemical interpretation difficult at first glance. The relevant chemical information can then be complicated to extract, especially if the raw data is noisy. There are several strategies to overcome these drawbacks, but weaknesses remain. As a consequence, a new alternative method is proposed to handle these interferences, the noise, and the rank deficiencies in the data and applied for the characterization of polycyclic aromatic compound (PAC) mixtures. It is based on effective truncated singular-value decomposition (MT-SVD) that does not require any prior knowledge of the raw data. The algorithm provides a valuable estimation of the global rank to choose on complex samples where selectivity problems are observed. It is a real alternative compared to other existing methods applied to the fluorescence matrix to filter the signal from noise or light scattering effects. The first exploratory results of the proposed algorithm are promising to handle matrix rank deficiencies as well as the effects of noise and light scattering on complex PAC mixtures.
| S-EPMC9281310 | biostudies-literature
Project description:In microarray data there are a number of biological samples, each assessed for the level of gene expression for a typically large number of genes. There is a need to examine these data with statistical techniques to help discern possible patterns in the data. Our technique applies a combination of mathematical and statistical methods to progressively take the data set apart so that different aspects can be examined for both general patterns and very specific effects. Unfortunately, these data tables are often corrupted with extreme values (outliers), missing values, and non-normal distributions that preclude standard analysis. We develop a robust analysis method to address these problems. The benefits of this robust analysis will be both the understanding of large-scale shifts in gene effects and the isolation of particular sample-by-gene effects that might be either unusual interactions or the result of experimental flaws. Our method requires a single pass and does not resort to complex "cleaning" or imputation of the data table before analysis. We illustrate the method with a commercial data set.
| S-EPMC263735 | biostudies-literature
Project description:We present a natural generalization of the recent low rank + sparse matrix decomposition and consider the decomposition of matrices into components of multiple scales. Such decomposition is well motivated in practice as data matrices often exhibit local correlations in multiple scales. Concretely, we propose a multi-scale low rank modeling that represents a data matrix as a sum of block-wise low rank matrices with increasing scales of block sizes. We then consider the inverse problem of decomposing the data matrix into its multi-scale low rank components and approach the problem via a convex formulation. Theoretically, we show that under various incoherence conditions, the convex program recovers the multi-scale low rank components either exactly or approximately. Practically, we provide guidance on selecting the regularization parameters and incorporate cycle spinning to reduce blocking artifacts. Experimentally, we show that the multi-scale low rank decomposition provides a more intuitive decomposition than conventional low rank methods and demonstrate its effectiveness in four applications, including illumination normalization for face images, motion separation for surveillance videos, multi-scale modeling of the dynamic contrast enhanced magnetic resonance imaging and collaborative filtering exploiting age information.
| S-EPMC5403160 | biostudies-literature
Project description:BackgroundBoth microarrays and quantitative real-time PCR are convenient tools for studying the transcriptional levels of genes. The former is preferable for large scale studies while the latter is a more targeted technique. Because of platform-dependent systematic effects, simple comparisons or merging of datasets obtained by these technologies are difficult, even though they may often be desirable. These difficulties are exacerbated if there is only partial overlap between the experimental conditions and genes probed in the two datasets.ResultsWe show here that the generalized singular value decomposition provides a practical tool for merging a small, targeted dataset obtained by quantitative real-time PCR of specific genes with a much larger microarray dataset. The technique permits, for the first time, the identification of genes present in only one dataset co-expressed with a target gene present exclusively in the other dataset, even when experimental conditions for the two datasets are not identical. With the rapidly increasing number of publically available large scale microarray datasets the latter is frequently the case. The method enables us to discover putative candidate genes involved in the biosynthesis of the (1,3;1,4)-beta-D-glucan polysaccharide found in plant cell walls.ConclusionWe show that the generalized singular value decomposition provides a viable tool for a combined analysis of two gene expression datasets with only partial overlap of both gene sets and experimental conditions. We illustrate how the decomposition can be optimized self-consistently by using a judicious choice of genes to define it. The ability of the technique to seamlessly define a concept of "co-expression" across both datasets provides an avenue for meaningful data integration. We believe that it will prove to be particularly useful for exploiting large, publicly available, microarray datasets for species with unsequenced genomes by complementing them with more limited in-house expression measurements.
| S-EPMC2562393 | biostudies-literature
Project description:Ultrasound contrast agents (UCAs) are designed to be used below 10 MHz, but interest is growing in studying the response of agents to high-frequency ultrasound. In this study, the subharmonic response of polymer-shelled UCAs with a mean diameter of 1.1 mum excited with 40-MHz tone-bursts of 1-20 cycles was analyzed. UCAs were diluted in water and streamed through a flow phantom that permitted single-bubble backscatter events to be acquired at peak-negative pressures from 0.75 to 5.0 MPa. At each exposure condition, 1000 single-bubble-backscatter events were digitized. Subharmonic content at 20 MHz was screened using a conventional and a singular-value-decomposition (SVD) method. The conventional method evaluated each event spectrum individually while the SVD method treated the 1000-event data set at one time. A subharmonic score (SHS) indicative of how much subharmonic content a 1000-event data set contained was computed for both methods. Empirical-simulation results indicated that SHSs obtained from the two methods were linearly related. Also, experimental data with both methods indicated that subharmonic likelihood increased with pulse duration and peaked near 2 MPa. The SVD method also yielded quantitative information about subharmonic events not available with the conventional method.
| S-EPMC2719484 | biostudies-other
Project description:High-dimensional data, such as those obtained from a gene expression microarray or second generation sequencing experiment, consist of a large number of dependent features measured on a small number of samples. One of the key problems in genomics is the identification and estimation of factors that associate with many features simultaneously. Identifying the number of factors is also important for unsupervised statistical analyses such as hierarchical clustering. A conditional factor model is the most common model for many types of genomic data, ranging from gene expression, to single nucleotide polymorphisms, to methylation. Here we show that under a conditional factor model for genomic data with a fixed sample size, the right singular vectors are asymptotically consistent for the unobserved latent factors as the number of features diverges. We also propose a consistent estimator of the dimension of the underlying conditional factor model for a finite fixed sample size and an infinite number of features based on a scaled eigen-decomposition. We propose a practical approach for selection of the number of factors in real data sets, and we illustrate the utility of these results for capturing batch and other unmodeled effects in a microarray experiment using the dependence kernel approach of Leek and Storey (2008, Proceedings of the National Academy of Sciences of the United States of America 105, 18718-18723).
| S-EPMC3165001 | biostudies-literature
Project description:Some statistical analysis techniques may require complete data matrices, but a frequent problem in the construction of databases is the incomplete collection of information for different reasons. One option to tackle the problem is to estimate and impute the missing data. This paper describes a form of imputation that mixes regression with lower rank approximations. To improve the quality of the imputations, a generalisation is proposed that replaces the singular value decomposition (SVD) of the matrix with a regularised SVD in which the regularisation parameter is estimated by cross-validation. To evaluate the performance of the proposal, ten sets of real data from multienvironment trials were used. Missing values were created in each set at four percentages of missing not at random, and three criteria were then considered to investigate the effectiveness of the proposal. The results show that the regularised method proves very competitive when compared to the original method, beating it in several of the considered scenarios. As it is a very general system, its application can be extended to all multivariate data matrices. •The imputation method is modified through the inclusion of a stable and efficient computational algorithm that replaces the classical SVD least squares criterion by a penalised criterion. This penalty produces smoothed eigenvectors and eigenvalues that avoid overfitting problems, improving the performance of the method when the penalty is necessary. The size of the penalty can be determined by minimising one of the following criteria: the prediction errors, the Procrustes similarity statistic or the critical angles between subspaces of principal components.
| S-EPMC10407287 | biostudies-literature