Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [svd]

Singular Value Decomposition (SVD) is a decomposition (factorization) of rectangular real or complex matrix into the product of a unitary rotation matrix, a diagonal scaling matrix, and a second unitary rotation matrix.

Filter by
Sorted by
Tagged with
2
votes
0answers
44 views

Singular vectors of s1 for tiny dense matrices

I have a function whose main bottleneck is finding a(ny) singular vector pair in the space of the largest singular value, along with the singular value itself. This is done a huge number of times. ...
0
votes
1answer
50 views

Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$

Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$ Question What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
3
votes
1answer
84 views

Analytic formula for leading eigenvector of $uu^T + vv^T$?

Let $u$ and $v$ be nonzero column vectors of size $n$ and consider the $n \times n$ positive-definite matrix $A:=uu^T + vv^T$. In this post https://math.stackexchange.com/a/112201/168758, the ...
3
votes
1answer
70 views

Whitening transformation does NOT return a unit covariance matrix

For this question, I am using the following Wiki definition of Matrix whitening: Suppose $X$ is a random (column) vector with non-singular covariance matrix $\Sigma$ and mean 0. Then the ...
1
vote
0answers
41 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
8
votes
1answer
104 views

Finding the $i$-th largest eigenvalue of a matrix

Given a large matrix $A$ with eigenvalues $\sigma_1\ge \sigma_2 \ge \dotsc $, I want to determine only a subset of these values, say $\sigma_5,\sigma_8$ and $\sigma_{19}$. Is there an algorithm that ...
3
votes
1answer
273 views

Golub-Kahan-Lanczos Bidiagonalization Procedure implementation doesn't produce bidiagonal matrix

I'm trying to implement the aforementioned procedure using this website as a reference. At the end of the page the algorithm is described as follows: I think I've mapped the given algorithm to code ...
1
vote
0answers
73 views

finding null space to a complex matrix

I need to solve the following equation: $$ \begin{pmatrix} \frac{\omega^2}{c^2}\varepsilon_x-\mu_z^{-1}k_y^2-\mu_y^{-1}k_z^2 & \mu_z^{-1}k_xk_y & \mu_y^{-1}k_xk_z\\ \mu_z^{-1}k_xk_y &\...
2
votes
1answer
140 views

How we can use CUR decomposition in place of SVD decomposition?

I have understood how CUR and SVD works, but have not been able to understand the following. How can we use CUR in place of the SVD decomposition? Do the $C$ and $R$ matrices in the CUR follow the ...
4
votes
1answer
269 views

Nystrom approximation of SVD for asymmetric matrices

Suppose I have a symmetric matrix $K$. Subdivide $K$ into pieces as $$K=\begin{pmatrix} K_{11} & K_{12} \\ K_{21} & K_{22}\end{pmatrix},$$ where $K_{21}=K_{12}^\top$. Then, the Nystrom ...
1
vote
2answers
179 views

Inverting big symmetric and singular matrices

In this post I found a very similar probem to the one I have, but not a satisfactory answer for my purposes. I have a set of matrices $C_\ell$. They are exactly symmetric by construction. ...
4
votes
1answer
472 views

Poor SVD reconstruction of singular matrix

I am trying to calculate the singular value decomposition of this matrix using numpy.linalg.svd . However, reconstructing the matrix from the SVD gives a poor ...
1
vote
0answers
154 views

Best algorithm for inversion of matrix spanning many orders of magnitude [duplicate]

I have a very similar problem to the one described in Calculate inverse of dense matrix with entries of very different magnitude. The reason why I am opening a new question is because as far as I ...
9
votes
2answers
467 views

How much regularization to add to make SVD stable?

I've been using Intel MKL's SVD (dgesvd through SciPy) and noticed that results are are significantly different when I change precision between ...
1
vote
0answers
395 views

Pseudoinverse of a large sparse matrix in r

This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r I am trying to calculate the pseudoinverse of a large sparse ...
3
votes
1answer
3k views

Block-matrix SVD and rank bounds

Assume, we have an $m\times n$ block matrix $M=\left[\begin{array}{c c}A&C\\B&D \end{array}\right]$, where $A$ is an $m_1 \times n_1$ matrix of rank $k_A$. $B$ is an $m_2 \times n_1$ matrix ...
2
votes
0answers
130 views

Generalized eigenvalue with null space

Define $S\in\mathbb{R}^{n\times n}$ as $$S:=H+Q^\top V^{-1} Q.$$ $H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for ...
7
votes
1answer
260 views

What is the fastest way to compute the sum of the singular values of a matrix?

Is there a faster way to compute the nuclear norm (trace norm, sum of singular values) of a matrix A than computing SVD(A) directly (or diagonalizing A^*A)? I am particularly interested in the case ...
2
votes
0answers
56 views

Under what circumstances does Elemental's distributed SVD not work? [closed]

I am playing around with Elemental's distributed singular value decomposition and am running into two particular issues. Building the test at tests/lapack_like/SVD.cpp, and running with ...
7
votes
2answers
166 views

Lanczos algorithms for Hermitian system with Toeplitz kernel

Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector ...
2
votes
0answers
49 views

Optimal ordering in Jacobi SVD algorithm

In Jacobi SVD algorithm as given here every pair of columns of the matrix is orthogonalized until convergence. I want to know that how does the order of selection of the pair of columns affect the ...
2
votes
1answer
95 views

Condition Number of Rectangular Matrices

The 2-norm condition number can be easily extended to rectangular matrices. I'm wondering if the inequality for the product of matrices still holds in that case, i.e., $\operatorname{cond}(AB) \leq \...
1
vote
2answers
200 views

Efficient methods to solve large dense singular least square problem (linear system)

I am trying to solve a singular linear least square problem: $$minimize: \phantom{2} ||Ax-b||^2 \\ subject \phantom{2} to: \phantom{2} x \ge 0$$ Here $ A \in R^{n \times m} $, and $ n\lt m$. here m ...
2
votes
0answers
26 views

Choosing suitable polynomial degree based on information in advection stencil

I'm working on a finite volume advection scheme for unstructured meshes which uses a multidimensional polynomial weighted least squares fit for interpolating from cell centres onto faces. In 2D, the ...
1
vote
1answer
564 views

Iterative Closest Point Algorithm

I am currently working on an iterative closest point algorithm (in C++, see here). I understand the basic premise of an ICP algorithm. You have two point clouds (a target and a reference) and you ...
4
votes
1answer
403 views

Obtaining column vectors of pseudo-inverse of a matrix

I need to compute the pseudo-inverse of a very large rectangular dense matrix without any special structure or properties. I run out of memory/computing power and have no access to a large parallel ...
1
vote
1answer
188 views

Compare reconstruction of matrices using SVD

I'm interested in how much 'signal' is retained from including k singular values in a Singular Value Decomposition, but I'm having trouble conceptualizing (or ...
1
vote
1answer
467 views

On the fly/matrix free SVD of large sparse matrix

I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and ...
3
votes
2answers
1k views

SVD of large block-hankel matrix

I am trying to do SVD of a large block-hankel matrix for model order reduction (Low rank approximation). However, I quickly run into memory issues in forming the large Block-Hankel matrix and CPU ...
1
vote
1answer
263 views

Fast algorithms for computing only the generalized singular values (but not the vectors)

I am interested in computing only the generalized singular values, and was wondering if this was faster (and by how much?) than computing the full GSVD. In particular, I was wondering what the ...
2
votes
0answers
159 views

Using Centroid decomposition instead of SVD

This paper says centroid decomposition (CD) is an approximation to singular value decomposition (SVD). First I do not understand CD yet, since code is available I just want to try it out how it works ...
6
votes
3answers
1k views

Why is Matlab's SVD faster on skinny matrices than on fat matrices?

I noticed something odd today. I have a matrix X that is very skinny (20800 x 200), double precision real numbers, not sparse, ...
8
votes
4answers
3k views

Incremental SVD implementation in MATLAB

Is there any library/toolbox which has implementation of incremental SVD in MATLAB. I have implemented this paper, it is fast but does not work well. I tried this but in this also error propagates ...
4
votes
1answer
315 views

Using SVD to biorthogonalize left and right eigenvectors?

I have a set of left and right eigenvectors from an nonsymmetric eigenproblem, and I'd like to biorthogonalize them. I tried Gram-Schmidt, but this fails for most cases. I then read that the SVD is ...
1
vote
2answers
530 views

Are there any popular (paralleled) implementations of Lanczos methods for SVD/eigendecomposion?

I want to use it in Matlab or Java. Will these two languages be much slower for computing the algorithm compared to C, C++, in case efficiency is an important factor? I'm aware of that there's a ...
5
votes
1answer
110 views

Are there any algorithms “incrementally remove part of data (esp., old data)” from the existing SVD model of a data?

Sometimes it is meaningful to remove the influence of some old data from a SVD-based model, so as to reflect the most updated trends and provide more accurate results. I've seen there're incremental ...
0
votes
1answer
52 views

Signal balancing using SVD: notations and implementation in R

Hibbs et. al use SVD to balance the strength of different underlying signals in gene expression data using the following decomposition: $X_{m*n} = U_{m*n} \Sigma_{n*n} V^T_{n*n}$ In this case $U$ ...
3
votes
1answer
124 views

Find a single vector in the null space

I have a single sparse matrix $A$ for which I can easily compute $Ax$ and $A^*x$ and I would like to solve $\min(||Ax||) \text{ s.t. } ||x||=1$. I know the answer is the right singular vector ...
1
vote
1answer
356 views

Any relation between the singular values of each flattening matrices and the core tensor out of Tucker decomposition?

Before I know how to do tucker decomposition, I mistakenly thought the core tensor is only from combining the singular value matrices of the flattening matrices. Yes I know it is not now. For the ...
2
votes
1answer
292 views

LSA, SVD and the Frobenius norm

In Latent Semantic Analysis one uses the SVD to perform a dimensional reduction of the term-document matrix, via the Eckart-Young theorem. Now, the rank $k$ approximation obtained by E-Y is proven to ...
2
votes
1answer
454 views

SVD and HITS Algorithm Power Iterations

As we know, computing the authority (or hub) score of HITS ranking method, means to use the following matrix equation: $$ \textbf{a}^{k}=A^T A\textbf{a}^{(k-1)} $$ and apply the power iteration ...
0
votes
1answer
482 views

Truncated SVD implementation in Java

I need the Truncated SVD implementation in java. I need to pass a matrix of doubles and an integer value representing the rank where to filter out noise. In output i need a filtered matrix of doubles. ...
3
votes
1answer
203 views

singular value decomposition of a 2 x 2 complex matrix

This should be easy, but... I would like to express the singular value decomposition of a 2 x 2 complex matrix $A$ as function of its coefficients $A_{ij}$. In "closed form", no intermediate values, ...
11
votes
0answers
472 views

Fast Eigenvalue and SVD Solver for Structured Matrices

I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to ...
1
vote
1answer
1k views

How can I reuse the SVD of matrix A to solve LS problems for both A and its transpose via Eigen C++?

If $A\in R^{m\times n}, b\in R^m, c\in R^n$, if I need to solve the least square problems via SVD of $A$ and $A^T$, i.e. I need to solve the least square solutions to following linear systems via ...
11
votes
1answer
1k views

Purely rotational least squares match

Could anyone recommend a method for the following least-squares problem: find $R \in \mathbb{R}^{3 \times 3}$ that minimizes: $\sum\limits_{i=0}^N (Rx_i - b_i)^2 \rightarrow \min$, where $R$ is a ...
10
votes
2answers
2k views

computing the truncated SVD, one singular value/vector at a time

Is there a truncated SVD algorithm that computes the singular values one at a time? My problem: I would like to compute the first $k$ singular values (and singular vectors) of a large dense matrix $M$...
5
votes
1answer
731 views

Inverse iteration to find the null singular vector of a rank-deficient matrix

I have an $n \times n$ unsymmetric matrix $A$ that results from the discretization of an ill-posed Poisson problem, and thus is rank-deficient with null space of dimension one. I want to compute just ...
26
votes
10answers
7k views

Robust algorithm for $2 \times 2$ SVD

What is a simple algorithm for computing the SVD of $2 \times 2$ matrices? Ideally, I'd like a numerically robust algorithm, but I'll like to see both simple and not-so-simple implementations. C code ...
10
votes
1answer
944 views

Why SVD is talk about less than QR and LU for sparse matrix?

For example the C++ sparse matrix libraries I used -- Eigen and SuiteSparse, they seem not to have any SVD funcitionality for sparse matrix. So just curious, is SVD more difficult than QR/LU for ...