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

learn more… | top users | synonyms

1
vote
0answers
43 views

Why is it difficult (and not precise) to compute the rank of large matrix numerically?

I have a general question. I have a large square matrix ($n> 1000$) and it is needed to compute the rank of this matrix. I am reading that the computation of the rank for large matrices, can make ...
1
vote
1answer
37 views

Is an orthogonal matrix necessarily a permutation matrix?

Is an orthogonal matrix necessarily a permutation matrix? I believe the answer is no as a permutation matrix is a special case of an orthogonal matrix, but I am having a trouble finding a ...
0
votes
1answer
15 views

Proof with an Artificial Power Method

Suppose $A$ is $m\times m$ and has a complete set of orthonormal eigenvectors, $q_1, \ldots , q_m$, and with corresponding eigenvalues $\lambda_1,\ldots , \lambda_m$. Assume that the ordering is such ...
1
vote
2answers
17 views

Robustly map rotation matrix to axis-angle

The Wikipedia article for rotation matrix gives the following formula for converting from rotation matrix, $Q$, to axis-angle, $u$ and $\theta$: $$ \begin{align} x &= Q_{zy} - Q_{yz} \\ y &= ...
0
votes
0answers
12 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve $Ad^{(n)...
0
votes
0answers
26 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use it,...
0
votes
1answer
27 views

on a characterization of convergent matrices

Let $A\in \mathbb R^{n\times n}$ a matrix. It's known that the following statements are equivalent: 1) $A$ is convergent, namely $\lim_{k\to\infty}(A^k)_{ij}=0$ 2) $\lim_{k\to\infty}||A^k||=0$ for ...
0
votes
1answer
30 views

eigenvalues lesser than 1 implies affine maps are eventually contractive

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said $\textbf{contractive}$ if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ ...
1
vote
1answer
28 views

Determining the most appropriate set of eigenmodes for a modal decomposition of an experimental data set

I have a complex vector of the transverse amplitude and phase distribution of a laser beam, derived from experimental data. When modelling these field distributions, ordinarily the eigenmodes of the ...
1
vote
0answers
30 views

Eigenvalue equation and the diffusion equation

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
0
votes
1answer
17 views

Diagonalizing a Block Matrix with one non-zero Block column

I am trying to diagonalize $(M+N) \times (M+N)$ matrix $G\Gamma_LG^\dagger\Gamma_R $$ = \left(\begin{array}{cc} 0_{M\times M} & A_{M\times N} \\ 0_{N\times M} & B_{N\times N} \end{array}\...
3
votes
1answer
55 views

eigenvalues lesser than $1$ implies contractive map

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said contractive if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ we have $d(...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
1
vote
1answer
75 views

why do we say SVD can handle singular matrx when doing least square? Comparison of SVD and QR decomposition

I don't quite understand why we say that QR decomposition doesn't handle singular matrix, while SVD does when they are used for least square problem? My example in Matlab seems to support the ...
0
votes
0answers
13 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
15 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \...
1
vote
0answers
33 views

Spectral relaxation of k-means clustering

I am working on a presentation on Spectral relaxation of k-means clustering (http://papers.nips.cc/paper/1992-spectral-relaxation-for-k-means-clustering.pdf) and I am a bit stuck. I understand ...
2
votes
0answers
22 views

Is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay

I'm studying for a test and I'd like to know is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay. I have no clue to verify the claim. Can anyone give me ...
1
vote
0answers
16 views

Is it possible to construct a consistent unstable one step method of order 2? why?

Is it possible to construct a consistent unstable one step method of order 2? why? I think the answer is no but I have no clue to prove it. Can anyone give me some explanations? Thank you in advance ...
1
vote
1answer
43 views

Proving Equality of the Induced Matrix Norm

I need to prove that the induced matrix norm satisfies $$\|A\| = \max_{\|x\| = 1} \|Ax\|$$ Here's what I've done so far, and I'm not sure how to make the connection. By definition, $$\|A\| = \max_{x\...
0
votes
0answers
18 views

question about dimensions.

$A\in\mathbb{R}^{n\times n}$, when solving $Ax=b$ numerically in projection method, we approximate the exact solution $x^*$ by $y$ in the subspace $K$ which has the dimension $m$. my textbook said $m$...
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
40 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
44 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
27 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
23 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
35 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
29 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
58 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
25 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
51 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
117 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
24 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
69 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
48 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
47 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
40 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 ...