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

learn more… | top users | synonyms

12
votes
3answers
427 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 ...
10
votes
2answers
902 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: ...
8
votes
6answers
505 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} ...
8
votes
2answers
197 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
1k 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 ...
8
votes
1answer
1k 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
4answers
591 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
1answer
112 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 ...
7
votes
1answer
152 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
254 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
159 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
1k 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 ...
6
votes
1answer
1k 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
400 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
207 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
119 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
253 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 ...
5
votes
6answers
1k 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
135 views

how can a matrix vector product reduce to a scalar?

I have an Excel spreadsheet with the following formula (paraphrased): ...
5
votes
2answers
473 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
787 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
1answer
135 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
288 views

Precision and performance of Euclidean distance

The usual formula for euclidean distance that everybody uses is $$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$ Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ...
5
votes
1answer
28 views

proving a theorem of alternative

I've read the following exercise in my book: Let $A\in\mathbb R^{m\times n},b\in\mathbb R^m,c\in\mathbb R^n$. Then exactly one holds: $Ax=0,c^t\cdot x=1$ with $x\geq0$ has a solution $A^ty\geq c$ ...
5
votes
0answers
74 views

IEEE 754 as a mathematical space

Integer operations in computers (i.e. 32-bit integers) probably can be represented best by modular arithmetic (because of integer overflows/underflows). What about IEEE 754 floating point arithmetic? ...
5
votes
0answers
152 views

numerical linear algebra tricks for repeated sums and inversions with symmetric positive-definite matrices

I'm doing the following procedure to get the max-likelihood estimate of a matrix-variate normal distribution from $r$ samples of matrices in $\mathbb{R}^{n \times p}$ (algorithm from Dutilleul ...
5
votes
0answers
73 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 ...
4
votes
3answers
461 views

Books for Numerical linear algebra

I'am looking for some books for studying Numerical linear algebra methods. It could be on english or russian ​​languages, and Maple or Matlab examples preferable, but it also can be C/C++/Formal code. ...
4
votes
1answer
90 views

$\delta$ Notation in linear algebra

In this equation below, what is $\delta_{l,q}$ denoting? Is $\delta$ a standard notation, or anything to do with all one's or the basis matrix etc? $$A_{ij}=\delta_{l,q}\left(\sum_{h=1}^n B_{l,h} + ...
4
votes
4answers
142 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 ...
4
votes
1answer
444 views

Algorithm for solving sparse equality-constrained least squares

I have a diagonal, positive-definite inner product matrix $M$ and want to find a minimizer of $$\min_q \frac{1}{2} \|q-q_0\|_M^2\qquad \text{s.t.}\qquad C^Tq+c_0 = 0,$$ where $q_0, c_0$, and $C$ are ...
4
votes
1answer
629 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 ...
4
votes
2answers
403 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? ...
4
votes
2answers
868 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 ...
4
votes
1answer
2k 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 ...
4
votes
1answer
2k views

Linear least squares with inequality constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. ...
4
votes
2answers
446 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 ...
4
votes
4answers
244 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
4
votes
1answer
127 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 ...
4
votes
1answer
135 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
4
votes
2answers
79 views

Norm “maintaining” matrices

Let $A$ be an $m\times n$ matrix such that $m < n$. I would like to know the conditions on $A$ such that the following is true: $$\|Ax\| \leq \|Ay\| \implies \|x\| \leq \|y\|$$ It can easily be ...
4
votes
2answers
252 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 ...
4
votes
1answer
92 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 ...
4
votes
1answer
66 views

Help in Proving a theorem

For the last few days I am trying to prove Result 2 which I have written below that uses the concepts of matrix decompostions to write matrix $A$ in the block form. I need help to prove this ...
4
votes
1answer
92 views

solve $ y = (A+B^{-1})x $ for $x$

I wish to solve numerically for $x$, $$ y = (A+B^{-1})x $$ with $A, B$ positive definite. So, $$ x = (A+B^{-1})^{-1}y $$ I would like to avoid calculating $B^{-1}$ since that's generally bad. ...
4
votes
1answer
274 views

Solving for specific entries in a Lyapunov Equation

Let $A$ be a $2n\times 2n$ real matrix with the following structure \begin{equation} A = \left(\begin{matrix} 0 & -I \\ K & S \end{matrix}\right) \end{equation} with all sub-matrices of size ...
4
votes
2answers
328 views

Incremental approach of calculating the Singular Value Decomposition

I have a fairly large array, a billion or so by 500,000 array. I need to calculate the singular value decomposition of this array. The problem is that my computer RAM will not be able to handle the ...
4
votes
1answer
407 views

How do I numerically calculate a function from its noisy gradient using “global integration”?

I have the model $\ s(x,y)=x^2+y^2, 0 \leq x \leq 1, 0 \leq y \leq 1 $. Instead of observing the model directly I am observing the derivatives of the model + some noise (e): $\ p(x,y)=s_x+e, ...
4
votes
1answer
68 views

Need little hint to prove a theorem from a paper

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
4
votes
1answer
127 views

Show the space spanned is an invariant subspace

Let $A$ be real and let $\lambda = \alpha + i \beta$ be a complex eigenvalue of $A$ with eigenvector $x + iy$, show that the space spanned by $x$ and $y$ is an invariant subspace of $A$. What I ...