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

learn more… | top users | synonyms

1
vote
1answer
38 views

Proving that $I-EA^{-1} = I+EA^{-1} + o(RelError(\tilde{A},A))$

Let $A\in\mathbb{R}^{n\times n}$ be a non-singular matrix and let $\tilde{A} = A-E$ be an approximation of $A$. The relative error of this approximation is $$RelError(\tilde{A},A) = \frac{\| \tilde{A}-...
2
votes
1answer
22 views

Block Matrix Nonsingular $\iff v^T A^{-1} u\neq 0$

Here is the given question and my work so far: Question: Let $A$ be an $n \times n$ invertible matrix, and let $u$ and $v$ be two vectors in $\mathbb{R}^n$. Find the necessary and sufficient ...
1
vote
1answer
38 views

MATLAB “back slash” computation [closed]

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below: Note: all of these are for m = 5000 1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; ...
2
votes
0answers
39 views

LU Decomposition vs. QR Decomposition for similar problems

Suppose I want to solve the 2D Poisson equation with Neumann boundary conditions. The solution is non-unique up to an additive constant. I have previously asked a related question here for the 1D ...
0
votes
0answers
24 views

Applications of Khatri-Rao matrices

I'm interested in what applications there are for Khatri-Rao matrices, and in particular for solving linear systems of equations involving Khatri-Rao matrices. A Khatri-Rao matrix is a block matrix ...
1
vote
0answers
21 views

Is there a way to find if there exists a solution such that all the variables in a system of linear equations are either 0 or 1 in P time?

Note this is different from Binary Integer Programming as it does not involve inequalities. An example would be a+b = 1. A solution would be a = 0, b = 1. I just want 1 solution, or even if there ...
0
votes
0answers
19 views

Why does biconjugate gradient (BiCG) work for nonsymmetric matrices?

After looking through the derivation of CG, I understand why it requires the coefficient matrix $A$ to be symmetric, since the property is used to produce a short recurrence relation for the ...
0
votes
1answer
32 views

Householder reflector which reflects a given vector through given subspace

I want to construct Householder reflector which reflects any vector $x \in \mathbb {R}^{n}$ through $r$ dimensional subspace $W$ of $\mathbb {R}^{n}$. Also, I want to calculate computational ...
1
vote
0answers
28 views

Numerical issues with matrix exponential for diagonalizable matrix

I am learning about computation of matrix exponentials, and have come across the technique: $$ e^A = U \operatorname{diag}(e^{\lambda_1}, e^{\lambda_2}, \ldots, e^{\lambda_n}) U^{-1}$$ Where the $\...
2
votes
0answers
57 views

Eigenvalues of a sum of matrices given eigenvalues of different sum

Firstly, what I want are the eigenvalues of a sum of matrices $(A + C)$. I am not asking how to express them in terms of the eigenvalues of the summands*. What I am hoping for is that there may be ...
1
vote
0answers
15 views

$Q$ is perfectly conditioned with respect to the 2-condition number.

Show that if $Q$ is orthogonal, then: $||Q||_2 = 1$, $||Q^{-1}||_2=1$, and $\kappa_2(Q)=1$. Tell me if I'm wrong but, I'm at if $||QQ^T||_2 = ||I||_2$ then $||QQ^T||_2 = 1$ which implies that $...
0
votes
3answers
56 views

Show that if $Q$ is orthogonal, then $Q^{-1}$ is orthogonal?

I know this should be basic and easy, but as I'm going through my book, I just can't seem to get this to work. Show that if $Q$ is orthogonal, then $Q^{-1}$ is orthogonal? I assume that ...
1
vote
1answer
23 views

Condition number equals its inverse.

How could you show that $\kappa(A)$ = $\kappa(A^{-1})$? And that for any nonzero scalar c, $\kappa(cA)$ = $\kappa(A)$? Maybe a little explanation as to some intuition behind this as well.
1
vote
1answer
50 views

Prove 1-Norm is a Norm

I am just curious how you would simply prove that a 1-norm is a norm. Step-by-step would be very helpful. Proofs are not my strong point. Thank you!
4
votes
0answers
113 views

Solving linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= \begin{...
2
votes
0answers
23 views

Why use the logarithm of the relative error?

In my numerical analysis course, we had an assignment to use MATLAB to numerically solve the Poisson Equation $-\nabla\cdot\nabla u = 0$ in one dimension. We computed the numerical solution, plotted ...
0
votes
0answers
27 views

Simplifying matrix expressions with LU decomposition?

If $A, B, C$ are $n \times n$ matrices, with $B$ and $C$ nonsingular, and $b$ is a vector of size $n$, how could one determine $$x = B^{-1}(2A + I)(C^{−1} + A)b?$$ I assume the solution has to do with ...
0
votes
0answers
20 views

How to derive this formula for numerical differentiation? [duplicate]

I've read from a book that numerical differentiation for a point $x_i$ can be obtained by taking a linear combination of function values of other points $f(x_j)$. I don't have a clue how the ...
-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 ...
1
vote
1answer
47 views

How to derive the Vandermonde Determinant?

I watched this video https://www.youtube.com/watch?v=87iJTcXqTKY explaning the Vandermonde Determinant I understood everything but I was wondering why the guy never mentioned the (-1)^(i+j) term used ...
0
votes
1answer
40 views

Solve matrices both algabraic and numerically

Can someone explain me to what to do here? I don't understand the question, or how to solve the problem. Should I use some theorems, to solve it?
1
vote
3answers
46 views

How to connect the definition of eigenvectors from linear algebra to their definition in Machine Learning

In Linear algebra the eigenvectors of a matrixs are these vectors that don't change their direction after applying this matrix( as a Transformation) to the space. But In machine learning (PCA to be ...
0
votes
1answer
29 views

Solving an equation involving the root of a quartic

Given that $ a = ((k-3)\sqrt{v})/s$ where $k$ and $v$ are known. I have to solve the following equation for $s$: $$q(a,b) = s \sqrt{v},$$ where $b = 1.08148a^2+\epsilon$ and $\epsilon>0$ a very ...
1
vote
0answers
34 views

Is this a correct way to approximate a derivative

I have some function $S(\hat y)$ which I want to approximate its derivative with respect to a vector. It's a tad complicated, I'll try and explain. $S$ is a function of $\hat y$ only, but $\hat y$ is ...
1
vote
1answer
55 views

Matrix equation involving pseudoinverse and trace

Let $P$ be an unknown complex $m \times n$ tall matrix ($m\geq n$, full column-rank), and $D$ a known real $m \times m$ diagonal matrix with positive entries. Is there a solution for $P$ from the ...
1
vote
1answer
38 views

Numerical diagonalization of a random hermitian matrix $H=U\Lambda U^{-1}$: enforce uniqueness and uniformity of $U$

I've stumbled across this seemingly simple question, but I could not find a satisfactory answer. Suppose I have a complex hermitian random matrix $H$. It can be diagonalized by a unitary ...
0
votes
0answers
27 views

Is $ \| \sum_{i \in [k]} \otimes^3 v_i - T \|_F^2 + \theta \| \sum_{i \in [k]} \otimes^3 v_i \|_F^2$ convex?

I am trying to find the minima of the following equation with respect to $v_i$, $i \in [k]$, to solve an optimization problem but I can't manage to make (stochastic or not stochastic, neither of them) ...
0
votes
0answers
49 views

Prove Norm Theorems

I have the following as given: Let $A \in C^{m\times m}$. Then: 1) $$\lVert A\rVert_1 =\sup_{v\in C^m \setminus\{0\} }{\lVert A_v\rVert_1 \over \lVert v\rVert_1} = \max_{j} \sum_i |a_{ij}|$$ How can ...
1
vote
1answer
65 views

Numerically Solving a Poisson Equation with Neumann Boundary Conditions

The Problem Suppose I have an equation of the form $\nabla^2 \phi(x) = f(x)$ on the interval $A \le x \le B$, where $f(x)$ is known and $\phi(x)$ is unknown. I have Neumann-type boundary conditions: $...
1
vote
1answer
14 views

inequality in compressed sensing

Let $h\in R^n$ is a k-sparse vector, then how can i prove this inequality $$||h||_p\leq k^{1/p-1/q}||h||_q\ \ ,\forall p\in[1,q]$$ where $q\geq 1.$ please help.
0
votes
1answer
20 views

principle component analysis - manual calculation - problem finding axis and eigenvectors on approximated covariance matrix

For the sake of a future tutorial video, I'm trying to manually perform the calculation of the principle axis and associated variances. Of course i'm trying to compute the eigenvectors and ...
2
votes
0answers
56 views

Faster Cholesky factorization of $diag(\mathbf{x}_{i}) \otimes \mathbf{A} + \mathbf{B}$ for $i=1,\ldots,n$?

I have many positive integer vectors $\mathbf{x}_{i} \in \mathcal{N}^{d_1}$, $i=1,\ldots,n$, a p.s.d. matrix $\mathbf{A} \in \Re^{d_2\times d_2}$ and a p.s.d. matrix $\mathbf{B} \in \Re^{d_1d_2\times ...
2
votes
1answer
65 views

show that $\lambda_{max}(B^{-1}A) \leq 1$ (eigenvalues, matrices, preconditioning)

I'm trying to get more familiar with eigenvalues and matrices but struggle to see the following: $\lambda_{max}(B^{-1}A) \leq 1$ $A \in \mathbb{R}^{n \times n}$ is symmetric, positive definite ...
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 &...
1
vote
1answer
32 views

Calculating the determinant by upper triangular reduction - can you check if it's correct?

Exercise: Calculate $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ -x & x & 0 & \dots & 0 \\ 0 & -x & x & \dots & 0 \\ \dots & \dots & \...
0
votes
0answers
16 views

Minimising two interdependent equations with least squares regression.

Originally, I had a set of points in three dimensional space that I was fitting using linear regression. So my model is $$Y = \alpha A+ \beta B$$ where $Y = \{y_i\}$ is the dependent variable, and $...
2
votes
1answer
59 views

Doubts on inverse power method

I found written that if matrix A is real and you use the Power method to find eigenvalues then "If the matrix and starting vector are real then the power method can never give a result with an ...
0
votes
0answers
17 views

condition number of a matrix with diagonal ones and constant else. [duplicate]

Consider the matrix $$A=\left(\begin{array}{ccccc} 1 & c & \cdots & c\\ c & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & c\\ c & \cdots & c & 1\\ \...
1
vote
1answer
92 views

Fastest way to solve linear system with block symmetric banded/Toeplitz matrix

I have a matrix of the following form: The size of the matrix may grow to be large, but the general pattern of being blockwise symmetric and banded (with 5 bands) will always hold. What is the ...
1
vote
1answer
50 views

Finding the Coefficient Matrix of a Spring-Mass System

So as part of a class in numerical linear algebra, we're exploring the topic of banded matrix system. I've come across a problem that involves Hooke's Law, but I'm having a little difficulty ...
0
votes
1answer
29 views

SVD for Seam Carving

Could SVD be used for Seam Carving ? I am making a small program for a uni course and I'm looking for different ways to calculate pixel energy; which made me come across SVD. Among others, I have ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
0
votes
1answer
31 views

How to find a number greater than the largest (smaller than the smallest) eigen value of a matrix efficiently?

I have a symmetric matrix $A$, I want to find a number say $\lambda_1$ which is greater than $\lambda$,i.e. the largest eigen value of the matrix $A$. It doesn't need to be equal to $\lambda$. But it'...
0
votes
2answers
30 views

$LU$ Factorization, improving upon stability

I was wondering when we add partial pivoting to an $LU$ factorization to a matrix $A$ it supposedly changes the data structure but improves the overall algorithm since we get better numerical ...
2
votes
0answers
29 views

Iterative methods: What happens when the spectral radius of a matrix is exactly 1?

I know that an iterative method (I'm using Jacobi and Gauss-Seidel in this case) will converge iff the spectral radius (max absolute value of eigenvalues) of its iterative matrix is strictly less than ...
1
vote
0answers
35 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
2
votes
1answer
41 views

Determining symmetricity of a matrix by multiplying with random vectors?

Stemming from an approach in a hint/answer to this question here. The idea is presented to determining wether a matrix is symmetric or not by measuring the following: $$e = \|({\bf Av})^T - ({\bf v}^...
1
vote
2answers
85 views

Is there an iterative way to evaluate least squares estimation?

Suppose to have a set of data $\{y_i, u_i\}_{i=1}^m$, where $y_i \in \mathbb{R}$ and $u_i \in \mathbb{R}^n$. The claim is that $$y_i = u_i^\top \theta + \varepsilon$$ where $\theta \in \mathbb{R}^n$...
0
votes
1answer
40 views

Prove there exist such that $A = [T]_\beta$ and $B = [T]_\gamma$ [closed]

Let $A$ and $B$ be similar $n \times n$ matrices. Prove that there exists an $n$-dimensional vector space $V$, a linear operator $T$ on $V$, and ordered bases $\beta$ and $\gamma$ for $V$ such that $A ...
1
vote
3answers
42 views

upper bound of a function $n^{1/\log(n)}$

I have the following expression $n^{1/\log(n)}, \quad where \quad n \in [1, 10,000]$. When I solve this numericall, I get the resultant value 2.718282 for all $n \in [2, 10,000]$. On this basis, I can ...