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

learn more… | top users | synonyms

12
votes
3answers
458 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
1k 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
520 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
226 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
781 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
2k 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) ...
7
votes
1answer
247 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
162 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
291 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
161 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
3answers
557 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
208 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
128 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
274 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
1answer
197 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 ...
5
votes
3answers
145 views

how can a matrix vector product reduce to a scalar?

I have an Excel spreadsheet with the following formula (paraphrased): ...
5
votes
2answers
532 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
858 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
148 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
1answer
3k 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
588 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 ...
5
votes
1answer
237 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 ...
5
votes
2answers
1k 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 ...
5
votes
2answers
288 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
2answers
312 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
39 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
77 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
178 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
79 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
1answer
113 views

$A, B$ sparse imply $AB$ is sparse?

Today I read the claim that if $A$ and $B$ are sparse matrices, then $AB$ is also sparse. I didn't believe it at first, but could not exhibit a counterexample. So is this claim in fact true? If so, ...
4
votes
3answers
597 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
2answers
85 views

Rewriting the matrix equation $AX = YB$ as $Y = CX$?

Is it possible in general, if $A,B,C,X,Y$ are square and of the same dimensions? If so, does it generalize to non-square matrices (using a pseudoinverse)? I'm doing some curve fitting in which I have ...
4
votes
1answer
100 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
210 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
2answers
2k 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 ...
4
votes
1answer
495 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
2answers
36 views

Implementing trig functions for dual numbers

I'm curious, how do common trig functions get implemented for dual numbers? One way would be to use the power series definition, but that seems inefficient
4
votes
1answer
747 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
532 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
3k 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 ...
4
votes
1answer
725 views

Product of positve definite matrix and seminegative definite matrix

Let $A$ a spd (symmetric positive definite) matrix and $B$ a symmetric seminegative definite matrix. Is tr $AB \leq 0$ and more general is $AB$ seminegative definite? I know that tr $AB \leq 0$ ...
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
4answers
386 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
139 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
81 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
1answer
177 views

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

I want to find the least squares solution to Ax=b where A is a highly sparse square matrix. I found two methods that look like they might lead me to a solution: QR factorization, and singular value ...