Hot answers tagged

19 votes

Robust algorithm for $2 \times 2$ SVD

See https://math.stackexchange.com/questions/861674/decompose-a-2d-arbitrary-transform-into-only-scaling-and-rotation (sorry, I would have put that in a comment but I've registered just to post this ...
user avatar
13 votes

How much regularization to add to make SVD stable?

The singular value decomposition for a symmetric matrix $A=A^{T}$ is one and the same as its canonical eigendecomposition (i.e. with an orthonormal matrix-of-eigenvectors), while the same thing for a ...
user avatar
10 votes

Robust algorithm for $2 \times 2$ SVD

@Pedro Gimeno "I doubt it can be any more robust than that." Challenge accepted. I noticed the usual approach is to use trig functions like atan2. Intuitively, there shouldn't be a need to use trig ...
user avatar
9 votes
Accepted

Poor SVD reconstruction of singular matrix

Algorithms for the SVD, as more or less every classical linear algebra algorithm based on orthogonal transformations, are normwise backward stable, i.e., it should be guaranteed that $\frac{\|USV^* - ...
user avatar
8 votes

Incremental SVD implementation in MATLAB

Yes. Christopher Baker has implemented his incremental SVD method in a MATLAB package called IncPACK (archived on GitHub, within the imtsl project). It implements methods that are described in his ...
user avatar
8 votes

Robust algorithm for $2 \times 2$ SVD

I needed an algorithm that has little branching (hopefully CMOVs) no trigonometric function calls high numerical accuracy even with 32 bit floats We want to calculate $c_1, s_1, c_2, s_2, \sigma_1$ ...
user avatar
7 votes

Inverting big symmetric and singular matrices

Think of your matrix as block-diagonal with blocks $$ C_\ell = \begin{pmatrix} 0 & & \\ & D_\ell & \\ & & 0\end{pmatrix}. $$ Then it is clear that $$ C_\ell^{-1} = \begin{...
user avatar
6 votes

singular value decomposition of a 2 x 2 complex matrix

The Pauli matrices and the identity matrix form an orthogonal basis of the space of $2\times 2$ matrices, so finding the expansion coefficients amounts to just a projection onto this basis (i.e., you ...
user avatar
6 votes
Accepted

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

No, there is nothing, as far as I know, unless you know approximately the location of these eigenvalues. As for methods that can compute a subset of the spectrum of a matrix, I know only of methods ...
user avatar
6 votes
Accepted

Rank of a double-precision augmented matrix

Q1: No. Here's a counter-example: ...
user avatar
6 votes
Accepted

Calculate determinant of unitary matrices based on SVD implementation

If you are prepared to go digging around in the fortran code: The SVD algorithm consists of a few parts: Bidiagonalization (usually using Householder reflectors) Use QR shifts to reduce the ...
user avatar
  • 1,169
5 votes

Robust algorithm for $2 \times 2$ SVD

This code is based on Blinn's paper, Ellis paper, SVD lecture, and additional calculations. An algorithm is suitable for regular and singular real matrices. All previous versions works 100% as well ...
user avatar
5 votes
Accepted

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

Yes. Take a look at the 2002 incremental SVD paper by Matthew Brand. In it, he discusses how to re-weight the SVD to dilute the influence of old data. He also has a 2006 paper on rank-1 updates of ...
user avatar
5 votes
Accepted

Block-matrix SVD and rank bounds

Let us begin with the exact singular value decompositions $A=U_{A}S_{A}V_{A}^{T}$, $B=U_{B}S_{B}V_{B}^{T}$, $C=U_{C}S_{C}V_{C}^{T}$, $D=U_{D}S_{D}V_{D}^{T}$. Then $$ M=\underbrace{\begin{bmatrix}U_{A} ...
user avatar
5 votes
Accepted

Matlab - Fast Computation of Truncated SVD / PCA

Pseudoinverse can be computed using the SVD $A = USV^\top$ by: $$ A^+ = V\Sigma^+ U^\top $$ where $\Sigma^+$ is formed from $\Sigma$ by taking the reciprocal of all the non-zero elements. With that in ...
user avatar
  • 2,139
5 votes

Calculate determinant of unitary matrices based on SVD implementation

For part 1: To my knowledge, the answer is no. For part 2: This question had several good answers, all of which were negative (there isn't really a faster way). I don't believe there is meaningful new ...
user avatar
4 votes

Incremental SVD implementation in MATLAB

One method to compute the svd of a matrix X is to first factor X=QR using the QR decomposition (for stability, use pivoting, so ...
user avatar
  • 201
4 votes

Robust algorithm for $2 \times 2$ SVD

LAPACK has an implementation of the svd of a 2x2 triangular matrix. It appears to be very robust. The routine is XLASV2. To apply to a regular 2x2 matrix, you can simply apply a single givens rotation ...
user avatar
  • 1,169
4 votes

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

As I already mentioned in the comments here is a possible answer which is backed by some experiments from AlexE in a further comment. The SVD in MATLAB uses the DGESVD from LAPACK, which is based on ...
user avatar
4 votes
Accepted

SVD of large block-hankel matrix

There are matrix free algorithms (algorithms that use only matrix-vector multiplications rather than working directly with the entries of the matrix) that can compute approximate values of a few ...
user avatar
4 votes

Incremental SVD implementation in MATLAB

Here is a method that can handle column additions: http://pcc.byu.edu/resources.html. I updated it to handle row additions: ...
user avatar
  • 229
4 votes

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

Pretty sure that what you want is Non-negative least squares. Plenty of implementations already exist, so you shouldn't have to write any code to get going. https://en.wikipedia.org/wiki/Non-...
user avatar
4 votes
Accepted

Nystrom approximation of SVD for asymmetric matrices

Nemtsov, Averbuchm, and Schclar's "Matrix compression using the Nyström method" (2016) seems relevant: The Nyström method is routinely used for out-of-sample extension of kernel matrices. We ...
user avatar
  • 3,091
4 votes

Asymptotic complexity of fixed-rank SVD

Yes. You can run rank-revealing QR on your matrix $A$, which will stop at step $k$ (hence effectively terminating in $O(mnk)$) and produce $A = QRP$, where $R$ has nonzeros only in its first $k$ rows, ...
user avatar
3 votes

Obtaining column vectors of pseudo-inverse of a matrix

The pseudo inverse $A^+$ fulfills: $A^+b$ is the minimimum norm solution of the least squares problem $\min_x \|Ax-b\|_2^2$. Hence, to calculate $A^+e_k$ by solving the respective optimization problem ...
user avatar
  • 1,728
3 votes
Accepted

Compare reconstruction of matrices using SVD

PSNR, the ratio between the peak power of the true signal and the power of the Gaussian noise, measures the amount of mathematical error introduced in an image by compression or noise introduction. ...
user avatar
  • 2,139
3 votes

Robust algorithm for $2 \times 2$ SVD

I have used the description at http://www.lucidarme.me/?p=4624 to create this C++ code. The Matrices are those of the Eigen library, but you can easily create your own data structure from this example:...
user avatar
  • 131
3 votes

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

You could try my MATLAB solver PDCO which uses an interior method and will be happy that your n < m. Use options.Method = 1 % the default d1 = 1e-4 d2 = 1
user avatar
3 votes

Condition Number of Rectangular Matrices

I guess I figured out the answer to my question. Suppose the SVD of $A = U \Sigma V^\ast$ (where $V^\ast$ is the conjugate transpose of the matrix $V$). Noting the fact that the unitary ...
user avatar
  • 562
3 votes

Lanczos algorithms for Hermitian system with Toeplitz kernel

How large are we talking, here? If the problem can fit onto a single node, you can likely just solve it through Hermitian matrix computations and call it a day, see SLEPc for fast implementations of ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible