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

learn more… | top users | synonyms

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
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
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 ...
2
votes
2answers
162 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
-1
votes
2answers
722 views

A projection $P$ is orthogonal if and only if its spectral norm is 1 [closed]

I have to show what the title says. A projection $P$ is orthogonal if and only if its spectral norm is $1$. I suppose I have to use the following identity: ...
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) ...
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: ...
3
votes
2answers
479 views

Generating unitary matrices numerically - “close” to the identity element

EDIT: broke this into two parts - for these were two different questions. For numerically obtaining the stabilities of a matricial equation, i need to generate an ensemble of matrices that are ...
1
vote
1answer
235 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
-2
votes
1answer
68 views

How was this formula for differentiation derived?

[![enter image description here][1]][1]Please tell me how this formula for numerical differentiation derived. I think it has something to do with Vandermonde Matrices but I am not quite sure how to go ...
6
votes
1answer
901 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
1k 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$ ...
2
votes
1answer
62 views

To create a special matrix !!

How to create a $N \times N$ matrix with $1$ and $-1$ as its elements, such that when this matrix is multiplied with its transpose the resultant matrice is $N \times \mathbb{I}_N$. Where $N$ is a ...
2
votes
1answer
59 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
2
votes
1answer
125 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
2
votes
1answer
124 views

I would like a hint in order to prove that this matrix is positive definite

Let $a_{ij}$ be a real number for all $i,j\in\{1,...,n\}$. Consider the matrix below. $$B=\begin{bmatrix} \sum_{k=1}^n(a_{1k})^2 & \sum_{k=1}^na_{1k}a_{2k} & \cdots & ...
5
votes
2answers
994 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
1answer
3k 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. ...
3
votes
1answer
56 views

$LU$ Factorization

Suppose the $A\in\mathbb{R}^{n\times n}$ is nonsingular and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^TA^{-1}e_j$,i.e., the $(i,j)$ element of $A^{-1}$ in ...
3
votes
3answers
771 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
1
vote
1answer
757 views

If modulus of each one of eigenvalues of $B$ is less than $1$, then $B^k\rightarrow 0$

Let $B$ be a $n\times n$ matrix and let $X$ be the set of all eigenvalues of $B$. Prove that if $|m|<1$ then $\lim \limits_{k\rightarrow\infty}B^k=0$, where $m=\max X$. Thanks. Actually, there ...
0
votes
1answer
47 views

How to substitute and matrix into a functions?

I have $f(x)=2*x_1 +x_2$ how to find $f(m*x)$ if m is a matrix $m=\begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$
-4
votes
1answer
89 views

Can we conclude that this matrix is definite positive? [duplicate]

Let $A$ be a $n\text{-by-}m$ matrix. Suppose that columns of $A$ are linearly independent. Can we conclude that $A^TA$ is definite positive? Could you help me with proof? Thanks.
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 ...
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 ...
4
votes
1answer
928 views

Why SVD on $X$ is preferred to eigendecomposition of $XX^\top$ in PCA

In this post J.M. has mentioned that ... In fact, using the SVD to perform PCA makes much better sense numerically than forming the covariance matrix to begin with, since the formation of ...
7
votes
1answer
182 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 ...
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 ...
4
votes
3answers
129 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
3
votes
2answers
170 views

How to efficiently solve a series of similar matrix equations using the LU decomposition

This is the problem I'm dealing with: Let $\sigma_1,\dots,\sigma_n \in \mathbb{R}$ and $b_1,\dots,b_n$ be column vectors of length $n$. Consider the system $$ (A - \sigma_jI)x_j = b_j, \quad ...
3
votes
1answer
2k views

Factorize a Symmetric matrix as an 'Approximation' with an outer product.

(deprecated-taken back based on discussion(OLD)) What is a good way to factor a symmetric matrix $X$ as an outer product of two vectors $u$ and $v$. i.e, Find two vectors $u$ and $v$ such that ...
6
votes
1answer
125 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
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 ...
5
votes
1answer
196 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 ...
2
votes
0answers
45 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
2
votes
1answer
54 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $$\|A^{-1}\|_{\infty}\leq\left[\min_i\left(|a_{ii}|-\left|\sum_{\substack{j\neq i}} a_{ij}\right|\right)\right]^{-1}.$$
2
votes
2answers
139 views

Lanczos vectors

I am trying to implement the Lanczos algorithm. If I implement it in Fortran or C, (i.e. in finite precision), will the vectors generated at each iteration still preserve their linear independence? ...
1
vote
0answers
404 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
135 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
1
vote
1answer
978 views

norm less than 1 matrix theory

Let $A$ be any $n \times n$ matrix and $\| \cdot \|$ be the matrix norm induced by vector norm on $\mathbb{R}^n$ (Euclidean n-dimensional space). If $\|I - A\| < 1$, then show that $A$ is ...
0
votes
0answers
45 views

Compression of a matrix A by V

I can't understand and even can't find any text on Compression of a matrix A by V. meaning if $B=V^*AV$ then B is called the compression of A. What does it mean???
0
votes
1answer
79 views

Interpolation of polynomials

let $f(x)=2^x$ and $x_0=1$, $x_1=2$, $x_2=3$. Use divided differences to compute the interpolation polynomial $P(x)$ satisfying $P(x_i)=f(x_i)$, i=0,1,2 and $P'(x_1)=f'(x_1)$ and estimate error ...
5
votes
1answer
1k views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...
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 ...
3
votes
3answers
2k views

Approximate a convolution as a sum of separable convolutions

I want to compute the discrete convolution of two 3D arrays: $A(i, j, k) \ast B(i, j, k)$ Is there a general way to decompose the array $A$ into a sum of a small number of separable arrays? That is: ...
3
votes
1answer
1k views

Unstable linear inverse problem: which “dampening” Tikhonov matrix should I use?

A linear inverse problem is given by: $\ \mathbf{d}=\mathbf{A}\mathbf{m}+\mathbf{e}$ where d: observed data, A: theory operator, m: unknown model and e: error. The Least Square Error (LSE) model ...
2
votes
1answer
548 views

equations solved with Newton's method by finding the zeros of functions?

I found this statement in one paper I read recently: This problem can be solved by finding the zero of functions: ...
2
votes
1answer
259 views

Finding vector $x$ so that $Ax=b$ using Householder reflections.

Assume $n\times m$ matrix $A$ and vector $b$ are given. I am looking for $x$ that satisfies $Ax=b$ in terms of linear least squares problem. Let $A=\begin{bmatrix} 1 & 1 & 1 \\0 & 1 & ...
2
votes
0answers
228 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
3answers
183 views

On integral of a function over a simplex

Help w/the following general calculation and references would be appreciated. Let $ABC$ be a triangle in the plane. Then for any linear function of two variables $u$. $$ \int_{\triangle}|\nabla ...