Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

13
votes
3answers
664 views

Fast computation/estimation of the nuclear norm of a matrix

The nuclear norm of a matrix is defined as the sum of its singular values, as given by the Singular Value Decomposition of the matrix itself. It is of central importance in Signal Processing and ...
12
votes
2answers
84 views

How to get the SVD of $2AA^T-\operatorname{diag}(AA^T)$ given $A$ and its SVD $A=USV^T$?

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. ...
10
votes
2answers
2k views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
10
votes
1answer
2k views

Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it: power iteration: take random ...
10
votes
0answers
386 views

Computing the SVD factorization on C++ (using the proof of the existence of the SVD factorization)

I am doing a C++ program that computes the SVD factorization of a real matrix A without using any known library of algebra that contains the implementation. In addition, QR descomposition is not ...
9
votes
3answers
1k views

I get a wrong determinant - why?

I'm trying to calculate the following determinant: $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ a_0 & x & a_2 & \dots & a_n \\ a_0 & a_1 & x & \dots ...
9
votes
6answers
599 views

$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)$ not diagonalizable

I would like to ask you about this problem, that I encountered: Show that there exists no matrix T such that $$T^{-1}\cdot \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} ...
9
votes
0answers
118 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
8
votes
1answer
695 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
8
votes
2answers
317 views

Advice in Bachelor Degree

First of all, I´m very sorry for my bad english, especially writing. Ok, for differents problems i´m studing a Bachelor degree in Mathematics. These degree is online. Now, the problem with my school ...
8
votes
1answer
2k views

What would be a good method for finding the submatrix with the largest sum?

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive ...
7
votes
2answers
16k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
7
votes
1answer
2k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
7
votes
5answers
2k views

Is there a faster way to calculate a few diagonal elements of the inverse of a huge symmetric positive definite matrix?

I asked this on SO first, but decided to move the math part of my question here. Consider a $p \times p$ symmetric and positive definite matrix $\bf A$ (p=70000, i.e. $\bf A$ is roughly 40 GB using ...
7
votes
3answers
2k views

Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?

I am given a $J \times J$ symmetric matrix $\Sigma$. For a subset of $\{1, ..., J\}$, $v$, let $\Sigma_{v}$ denote the associated square submatrix. I am in need of an efficient scheme for inverting ...
7
votes
4answers
450 views

Solve quadric equation system

How to solve this analytically(not a numerical solution)? For given real and symmetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $0\neq x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ ...
7
votes
1answer
183 views

Why would $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ be close to $A^{\dagger}$ when $A$ is with rank deficiency?

In many applications that is not with high requirements, it is common to use $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ or $A^{\text T}(AA^{\text T}+\lambda I)^{-1}$ ($\lambda$ is small) to ...
7
votes
1answer
86 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
7
votes
1answer
502 views

Sum of idempotent matrices is Identity

[Ciarlet, Problem $1.1-10$] Let $A_k$, $1 \leq k\leq m$, be matrices of order $n$ satisfaying $$\sum_{k=1}^mA_k\ =\ I.$$ Show that the following conditions are equivalent. $A_k = ...
6
votes
1answer
222 views

Generate arbitrary numerically invertable matrix

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I ...
6
votes
3answers
6k views

Power iteration smallest eigenvalue?

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both Power Iteration and Inverse Iteration. I can find them using the Inverse ...
6
votes
1answer
170 views

Computing very high powers of a particular Jordan block

Let $J$ be the following $k-by-k$ Jordan block: $$ J:= \begin{bmatrix} e^{i \theta} & 1 & \\ & e^{i \theta} & 1 \\ & & \ddots & \ddots \\ & & & \ddots & ...
6
votes
1answer
3k views

Block inverse of symmetric matrices

Let us assume we have a symmetric $n \times n$ matrix $A$. We know the inverse of $A$. Let us say that we now add one column and one row to $A$, in a way that the resulting matrix ($B$) is an $(n+1) ...
6
votes
3answers
2k views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
6
votes
4answers
896 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and ...
6
votes
1answer
902 views

Uniform sampling of points on a simplex

I have this problem: I'm trying to sample the relation $$ \sum_{i=1}^N x_i = 1 $$ in the domain where $x_i>0\ \forall i$. Right now I'm just extracting $N$ random numbers $u_i$ from a uniform ...
6
votes
1answer
1k views

Sum of eigenvalues and singular values

How one can prove that for a matrix $A\in \mathbb{C}^{n\times n}$ with eigenvalues $\lambda_i$ and singular values $\sigma_i$, $i=1,\ldots,n$, the following inequality holds: $$ \sum_{i=1}^n ...
6
votes
2answers
1k views

Algorithm to find an orthogonal basis (orthogonal to a given vector)

Let $K$ be a given integer, with $K$ even (and "large"). Let $\mathbf{v} \in \mathbb{R}^{K \times 1}$ be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix ...
6
votes
3answers
927 views

What are the real life applications of quadratic forms?

What are the real life applications of quadratic forms? I have used them to sketch conics but are there any other applications?
6
votes
4answers
221 views

Conditions for the equivalence of $\mathbf A^T \mathbf A \mathbf x = \mathbf A^T \mathbf b$ and $\mathbf A \mathbf x = \mathbf b$

I have an application where I have to minimize a cost function of the form: $J(\mathbf x) = \| \mathbf A \mathbf x - \mathbf b \|^2 \quad (1)$ By calculating the gradient, I derived that I have to ...
6
votes
1answer
127 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
6
votes
1answer
152 views

small rank solution of a matrix equation

Consider the matrix equation $$AX-XA = R$$ where $A$ and $R$ are given square matrices such that $\operatorname{rank}(R)=r$. How to establish conditions (necessary, sufficient, or both) on $A$ and ...
6
votes
0answers
477 views

Simulating from a Multivariate Gaussian without Cholesky

I'd like to draw a sample from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$, where $\mu$ is the mean vector (can assume it to be $\boldsymbol{0}$), and $\Sigma$ is a sparse positive ...
6
votes
0answers
95 views

Is there a way to exploit the fact that the covariance matrix has a blocked structure to more easily compute the multivariate normal density?

I'm trying to minimize the (negative) multivariate normal log likelihood (dropping constants): $$ \log |\boldsymbol\Sigma|\,+(\mathbf{x}-\boldsymbol\mu)^{\rm ...
5
votes
6answers
2k views

A book for self-study of matrix decompositions

I am a third year math student and I noticed that there are many uses for decomposing a matrix (I mean decompositions like SVD, LU etc'). Is there a good book for self-study of the subject ? Note ...
5
votes
3answers
1k views

What is the practical impact of a matrix's condition number?

Let's say I am trying to solve a square linear system $Ax = b$ for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by ...
5
votes
3answers
198 views

how can a matrix vector product reduce to a scalar?

I have an Excel spreadsheet with the following formula (paraphrased): ...
5
votes
1answer
5k views

Properties of sum of real symmetric, positive semi-definite matrices

I have two correlation matrices A and B. They are: Real symmetric (with ones on the diagonal) Positive semi-definite (eigenvalues are $\ge 0$) I want to try to prove that the average of these two ...
5
votes
2answers
742 views

When does an eigenvector of a matrix contain only a constant?

When I compute the eigenvectors of a certain matrix, the first of them is composed entirely of a single constant. What properties of a matrix lead to this result? Update By "a vector composed ...
5
votes
2answers
4k views

When do two matrices have the same column space?

Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices ...
5
votes
2answers
1k views

Least square principles with Lagrange multiplier

I have a function to minimize: $$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$$ subjected to this constraint: $$a_1^2+a_2^2+a_3^2=1$$ and $$a_4\geq0$$ I am trying ...
5
votes
2answers
998 views

Matrix Calculus in Least-Square method

In the proof of matrix solution of Least Square Method, I see some matrix calculus, which I have no clue. Can anyone explain to me or recommend me a good link to study this sort of matrix calculus? ...
5
votes
1answer
168 views

real eigenvalue

Let matrix $A$ be $$\begin{bmatrix} -5& 1& 0& 0\\ a &2& 1 &0\\ 0& 1 &1 &1\\ 0 &0&1& 0 \end{bmatrix}$$ where $a$ is a constant between 1 ...
5
votes
2answers
214 views

solution to $\min \|A-BXC \|$

I have the following problem. Let $A$, $B$ $C$ be real-valued matrices of size $m \times q$, $m \times n$, $p\times q$ respectively. I would like to find matrix $X$ of size $n\times p$ and maximum ...
5
votes
1answer
1k views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
5
votes
2answers
370 views

Check whether two subgroup of $GL(n,\mathbb Z)$ are conjugate

Suppose I have two finite subgroups of $GL(n,\mathbb Z)$. Is there an algorithm to find out whether these two belong to the same conjugacy class in $GL(n,\mathbb Z)$? I tried by using the Jordan ...
5
votes
1answer
2k views

9 point stencil for Laplacian operator

Given the following 9 point Laplacian \begin{align} -\nabla^2u_{i,j} = \frac{2}{3h^2}\left[5u_{i,j} - u_{i-1,j} - u_{i+1,j} - u_{i,j-1} - u_{i,j+1} - u_{i-1,j-1} - u_{i-1,j+1} - u_{i+1,j-1} - ...
5
votes
1answer
197 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm ...
5
votes
2answers
1k views

Why does the standard BFGS update rule preserve positive definiteness?

My class has recently learnt the BFGS method for unconstrained optimisation. In this procedure, we have a rank-1 update to a positive definite matrix at each step. This is specified as: $H_{k+1} = ...
5
votes
1answer
187 views

How can I tell which matrix decomposition to use for OLS?

I want to find the least squares solution to $\boldsymbol{Ax}=\boldsymbol{b}$ where $\boldsymbol{A}$ is a highly sparse square matrix. I found two methods that look like they might lead me to a ...