Skip to main content

Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
42 views

What is the "lifted system of linear equations"?

I am reading this blog post, where it says Here’s another variant of the same idea. Suppose we want to solve the linear system of equation $(D + uv^\top)x = b$ where $D$ is a diagonal matrix. Then we ...
nalzok's user avatar
  • 826
1 vote
0 answers
25 views

Is this generalization of determinant for a higher-order tensor a standard object?

The determinant of an $n$ by $n$ matrix $a$ can be defined as $$ \mathrm{det}(a)= \sum_{\sigma} \mathrm{sgn}(\sigma) a_{1,\sigma(1)} a_{2,\sigma(2)} \dots a_{n,\sigma(n)}$$ where $\sigma$ is a ...
Thomas's user avatar
  • 31
2 votes
0 answers
27 views

need a Jacobian of an orthonormal basis for the column space of a matrix $\mathbf{X}$

I require to find a linear decomposition of any tall matrix $\mathbf{X}$ $\in \mathbb{R}^{M \times N}$, where $M \geq N$, into some uniquely defined decomposition $\mathbf{X}$ $=$ $\mathbf{A}$ $\...
Tychus's user avatar
  • 31
1 vote
0 answers
32 views

Calculation of special subsets in high-dimensional binary matrices

I need to solve a rather specific problem related to binary matrices. The task is to count the number of specific "combinations", where "combination" means the following: this is ...
Disciple's user avatar
  • 345
0 votes
0 answers
19 views

Show integral of element-wise square of matrix exponential + I is invertible

Question: Let $\mathbf{Q}$ be a matrix whose eigenvalues have positive real parts, and let $\mathbf{B}$ be the matrix with entries \begin{equation} B_{ij} = \int_0^\infty ((e^{-Qt})_{ij})^2 dt. \end{...
porcupine1703's user avatar
1 vote
0 answers
50 views

Gerschgorin Circle Theorem and ordering of eigenvalues

Suppose $D\in \mathbb{R}^{n*n}$ is diagonal and $E\in \mathbb{R^{n*n}}$ be any matrix. Use Gerschgorin circle theorem to show that if $||E||_{\infty}<min_{i\neq j}|\frac{d_{ii}-d_{jj}}{2}|$ then ...
maths and chess's user avatar
1 vote
0 answers
32 views

Finding the least squares solution of a linear system based on a QR factorization

One method of finding the least squares solution of the following "augmented system" $$ \left[ \begin{matrix} I & A \\ A^T & O \end{matrix} \right] \left[ \begin{matrix} r \\ x \end{...
Olumide's user avatar
  • 1,261
0 votes
0 answers
27 views

The minimal eigenvalue of a symmetric matrix

Let $A$ be a symmetric matrix, and I want to show that for: $\epsilon>\lambda_{min}(A)$: $$A+\epsilon I>0$$ where $\lambda_{min}(A)$ is the minimum eigenvalue of $A$. My reasoning is as follows: ...
MathematicalPhysicist's user avatar
2 votes
0 answers
60 views

How exactly is Sherman-Morrison-Woodbury formula used in Kalman Filter

I have seen many places mentioned that Sherman-Morrison-Woodbury formula can be used in Kalman Filter to speed up the matrix inverse. Even the linked Wikipedia page mentioned that. I am not exactly ...
CuriousMind's user avatar
  • 1,634
0 votes
0 answers
33 views

Power method convergence rate

Let $\bf A$ is real symetric $n \times n$ matrix with eigenvalues satisfying $$ \lambda_{1} > \lambda_{2} \geq \lambda_{3} \geq \cdots > \lambda_{n} $$ and corresponding eigenvectors $x_{1},x_{2}...
maths and chess's user avatar
0 votes
0 answers
20 views

Reformulate an algorithm as a sequence of standard matrix operations

Consider the following code snippet ...
lehoj's user avatar
  • 1
0 votes
0 answers
16 views

7-point North-East ILU decomposition

I am using a 7-point difference operator (actually a 5-point difference operator with $b, f = 0$) to discretize the 2D model anisotropic problem. $ L_h $ in stencil notation is given. $ L_h = \begin{...
Sonny Jordan's user avatar
0 votes
2 answers
45 views

Symmetry preserving quadratic forms

Let $A$ and $S$ be conformable matrices with $S$ symmetric. One frequent annoyance is that the product: $$ \tilde{S} = ASA^\intercal $$ has antisymmetric components due to rounding. Is there a simple ...
Alex Nguyen-Le's user avatar
0 votes
1 answer
69 views

Issue in numerical integration of $\frac{1}{4\pi^{3/2}i}\int_Ce^{-\frac{z^3}{12}-tz}z^{-1/2}dz$

I am trying to numerically integrate the integral representation of $\operatorname{Ai}^2(x)$. The representation is $$\operatorname{Ai}^2(t)=\frac{1}{4\pi^{3/2}i}\int_Ce^{-\frac{z^3}{12}-tz}z^{-1/2}dz....
random0620's user avatar
  • 2,946
0 votes
0 answers
12 views

Can a Householder reflector (transform) be extended to a product of vectors?

Can a Householder reflector (transform) be extended to a product of vectors? Specifically, say we have two routines: $$\begin{align} h_m(i,x) =& (\alpha,v)\textrm{ where } x-\alpha\langle x,v\...
wyer33's user avatar
  • 2,572
0 votes
0 answers
9 views

Hessenberg matrix and Householder transformations

Let $A$ be a real unreduced upper Hessenberg matrix of order $n$. a)Show that A can be factored into A=QR, where R is upper triangular matrix and $Q=H_{1}H_{2}\ldots H_{n-1}$ orthogonal with each $H_{...
maths and chess's user avatar
0 votes
0 answers
95 views

Why do numerical eigenvector computations turn out different compared to symbolic formulas?

The following $A \vec x=\lambda \vec x$ should have 4 eigenvector solutions of the form Setting $c=1, m=1, p_x=1, p_y=1, p_z=1$, the eigenvalues should be $$\lambda = \pm 2$$ while the corresponding ...
James's user avatar
  • 802
0 votes
0 answers
113 views

Min-max of $|(z - x_1)(z - x_2)(z - x_3)|$

Trying to use the multi-parameter (3 parameter) Jacobi smoother on the 2D Convection Diffusion Equation with a $O(h^2)$ discretization. For the smoothing factor to be minimized, I have to minimize $$ \...
Sonny Jordan's user avatar
1 vote
1 answer
57 views

Derivative of a matrix formed of partial derivatives w.r.t a vector

I need to differentiate the following expression: $\tau_s = J_A^T(\boldsymbol{q_s}) \tau_m$ w.r.t $\boldsymbol{q_s}$ , where $\boldsymbol{q_s}$ is $2\times1$ vector and $J_A^T(\boldsymbol{q_s})$ is a $...
ClosedChain's user avatar
2 votes
0 answers
82 views

Estimation of the eigenvalue of a matrix [closed]

Let $A_n$ be a $n×n$ matrix with entries $a_{ij}=n-|i-j|$, let $\lambda_n$ be the largest eigenvalue of $A_n$, find $\lim_{n \to \infty} \frac{\lambda_n }{n^2}$ I find it hard to compute the ...
ddk's user avatar
  • 29
2 votes
1 answer
136 views

Lanczos convergence for symmetric matrix with eigenvalues $1,2,\cdots,2,100$

Suppose that $A$ is symmetric with eigenvalues $1,2,\cdots,2,100 \in \mathbb{R}^{100x100}$ and $b \in \mathbb{R}^{100}$ obtained by normalizing a standard normal random vector. Show that 1 and 100 are ...
jacopoburelli's user avatar
1 vote
0 answers
23 views

Compressed image using SVD draws a clear line between part that's blank and part with a drawing. Why? [closed]

I'm trying to compress grayscale images using SVD. This is the original image: Yes, there's a lot of blank space. I then choose the x% largest singular values, perform the transformed matrices ...
Elizabeth Middleford's user avatar
0 votes
0 answers
61 views

Why everyone talks SOR and nobody JOR?

Context I am considering both Jacobi and Gauss-Seidel to be well-established. Essentially, given a relaxation parameter $\omega$, we have the following two methods (we will indicate the result of ...
Simone Licciardi's user avatar
0 votes
0 answers
13 views

QR algorithm, equivalence of r shifts and r times 1 shift

Is it true that in general the general $QR$ algorithm applied to $A$, a multiple shift of degree $r$ is equivalent to a sequence of $r$ single shifts of degree $1$? (Assuming that no shift is an exact ...
Tora's user avatar
  • 31
1 vote
0 answers
76 views

The convergence of an iterative sequence

Let $\circ$ denotes the element-wise product, 1 denotes a vector of all ones, and $\lambda$ is a $d$-dimensional vector with all positive entries. I want to show the iterative form $$r_{t+1}=\lambda + ...
Nian Si's user avatar
  • 11
0 votes
0 answers
34 views

How do I create conjugate gradient method out of this Result?

How do I create conjugate gradient method out of this Result? My attempt:- If $A$ is symmetric positive definite, then solving $Ax = b$ is equivalent to minimizing the quadratic form $\varphi(x) = \...
Unknown x's user avatar
  • 849
2 votes
1 answer
75 views

If $A$ is symmetric positive definite, then solving $Ax = b$ is equivalent to minimizing the quadratic form $\varphi(x) = \frac{1}{2}x^T A x - x^T b$

If $A$ is symmetric positive definite, then solving $Ax = b$ is equivalent to minimizing the quadratic form $\varphi(x) = \frac{1}{2}x^T A x - x^T b$. $\textbf{Proof}$ We will consider changes of $\...
Unknown x's user avatar
  • 849
4 votes
2 answers
173 views

How to find an exact solution for $X=X^T \in \mathbb{R}^{n \times n}$ satisfying $AX=XA^T$ and $B=XC^T$

Assuming that I know that the following pair of equations has an exact solution: $$\exists X=X^T \in \mathbb{R}^{n \times n}: AX=XA^T,\ B=XC^T$$ For some matrices $A \in \mathbb{R}^{n \times n}$, $B \...
user9413641's user avatar
0 votes
0 answers
35 views

Envelope of matrix

Defining the envelope of a matrix as $\{(i,j) : J_i(A) \leq j< i\}$ where $J_i(A) := min\{j: a_{i,j} \neq 0\}$ I think we have the following theorem (correct me if wrong): Theorem: Given $A \in \...
jacopoburelli's user avatar
1 vote
0 answers
37 views

Derive Lanczos algorithm by imitating the derivation of Arnoldi iteration algorithm.

If A is Hermitian, then everything above simplifies (e.g., Hessenberg matrices turn into tridiagonal), and we get what is know in the literature separately as Lanczos iteration. My attempt:- ...
Unknown x's user avatar
  • 849
0 votes
0 answers
39 views

Recommended iterative numeric solver for generalized eigenvalue problem?

I have a generalized eigenvalue problem of the form $Av=\lambda Bv$, with the following conditions: $A$ is symmetric, but not sure if it is positive-definite. $B$ is diagonal with positive entries $A$...
trisct's user avatar
  • 5,261
0 votes
0 answers
14 views

Finding weights from a linear system

I have a dataset with n individuals and each individual is randomly assigned codes from m possible integer codes. The structure is such that if a person contains multiple codes then each code is ...
Calum's user avatar
  • 399
1 vote
1 answer
73 views

Solve ill-conditioned linear systems

Consider the following linear system of equations : $$Ax = b$$ When solving this system using MATLAB, I found that the condition number of matrix $A$ is extremely large, indicating that the system is ...
Elliot's user avatar
  • 31
0 votes
0 answers
52 views

Numerical Inverse of an integral

Let $f: \mathbb{R} \to (0, \infty)$ be a continuous function. Define $F: \mathbb{R} \to (0, \infty)$ by: \begin{equation*} F(x) = \int_{-\infty}^x f(t)dt \end{equation*} Clearly, $F$ is strictly ...
温泽海's user avatar
  • 2,487
-1 votes
1 answer
72 views

Iteratively finding matrix inverse from a given inverted matrix.

Let's say I need to find inverse of a bunch of matrices $A_0, A_1, ... A_n$. As the matrices are large (in my use-case), I am iteratively finding the inverse of each matrix $A_i$ using Newton matrix ...
Satya Prakash Dash's user avatar
2 votes
1 answer
68 views

What are the eigenvalues of a symmetric pentadiagonal Toeplitz matrix with zero tridiagonals?

I have the following symmetric pentadiagonal Toeplitz matrix, in which the superdiagonal and subdiagonal are zero. Please help me find the eigenvalues, in particular the largest one. The matrix can be ...
T V's user avatar
  • 23
0 votes
0 answers
14 views

The QR decomposition of upper Hessenberg matrix has the property that the $i+1,i$-th elements of $RQ$ are nonzero

The problem is:Let $A$ be a $n*n$ real invertible upper Hessenberg matrix and for all $i$, we have $a_{i+1,i}\neq 0$, let the $QR$ decomposition of it be $A=QR$, then I want to prove that $(RQ)_{i+1,i}...
YuerCauchy's user avatar
0 votes
0 answers
51 views

How does Self-Scaling Fast Givens QR work for (Regularized) Linear Least Squares

Basic Problem I need help to understand the Self-Scaling Fast Givens QR decomposition proposed in Anda A. A. & Park H., Self-Scaling Fast Rotations for Stiff and Equality Constrained Linear Least ...
MothNik's user avatar
0 votes
0 answers
59 views

Checking 'No-resonance' condition for the eigenvalues of a discrete Laplacian matrix with Dirichlet boundary condition

1-D discrete Laplacian matrix (finite difference scheme) has eigenvalues as (page-2 in ref.): $$\lambda_j = sin^2(\frac{j\pi}{2(N+1)});\ j\in \{1, 2, ..., N\}$$ Where $N$ is the number of ...
Manish Kumar's user avatar
1 vote
0 answers
29 views

Show that these two rank $1$ perturbations have the same eigenvectors

problem:let $D=diag(d_1,d_2,...,d_n)$, if $D+\alpha uu^T$ and $D+\hat{u}\hat{u}^T$ has the same set of eigenvalues, let these eigenvalues be $\lambda_1, \lambda_2,...,\lambda_n$, and satisfy $\...
YuerCauchy's user avatar
2 votes
1 answer
65 views

Solve the matrix equation $A = - B A B^T + C$ without matrix inversion or vectorization

Let $B$ and $C$ be two $n \times n$ matrices, which may or may not be nicely behaved. I would like to solve for the matrix $A$ in the following equation: $$ A = -B A B^T + C $$ This equation is linear ...
Zack's user avatar
  • 83
0 votes
1 answer
49 views

Using the definition, describe the backward error analysis and error bound of the eigen value problem.

By the definition 6.2.4.2, I tried to understand the cocept of backward error analysis of the Backward Error anlaysis for Eigenvalue problem, $f: \mathscr D\subset \mathbb C^{n,n}\to \mathbb C.$ $$f(A)...
Unknown x's user avatar
  • 849
0 votes
1 answer
45 views

Matlab qz algorithm not reliable

I programmed my own version of the qz algorithm and, while testing it's results using the matlab qz algorithm, I found a particular case where my solution reaches an upper-triangular matrix and matlab ...
Littlejacob2603's user avatar
1 vote
1 answer
133 views

Sensitivity of the eigenvalues to a change in a diagonal element.

I'm currently examining irreducible diagonally dominant matrices say A, i.e. $\exists i$ $|a_{ii}| > \sum _{i \not = j} a_{ij}$ and the corresponding graph G to the adjacency matrix A is strongly ...
zinsinho's user avatar
0 votes
0 answers
30 views

Relation between condition number and relative error

For the equation $Ax=b, A \in \mathbb{R}^{m*n}, x \in \mathbb{R}^n, b \in \mathbb{R}^m$, the condition number of $A$ gives an upper bound of the relative error in $x$ given a relative error in $b$: $||...
William Lin's user avatar
0 votes
1 answer
41 views

How to find the eigenvector of symmetric tridiagonal matrix

there are several questions related to this topic but only eigenvalues are considered, what about the eigenvectors? consider we have $$T= \left(\begin{array}{ccccc} a & b & 0 & \ldots &...
YuerCauchy's user avatar
5 votes
1 answer
155 views

If I can solve $Ax = b$ efficiently, is there a method to solve $(I+A)x=b$ efficiently?

Say if I already have the LU factorization of a square matrix $A$, is there an efficient way to get the LU factorization of $I+A$? (We may assume all the matrix I mentioned is invertible.) I know from ...
qdmj's user avatar
  • 555
6 votes
1 answer
89 views

Is it possible to apply the matrix inverse $(H(\textrm{Id}+F^T F)^{-1}H^T)^{-1}$ to a vector without explicitly calculating the inverse?

This is a continuation of this problem: Minimizing $\frac{1}{2}\|x-x_0\|^2 +\frac{1}{2}\|y-y_0\|^2$ subject to $F(x)=y, G(y)=b$ In this problem, to find the solution to the optimization problem, I ...
Kaira's user avatar
  • 1,565
8 votes
1 answer
233 views

Kalman Filter -- handling large covariance matrices with principal-component-like structures

I understand that the estimation of the covariance matrices are the important part of the Kalman filter. However in my use case my covariance matrices are really big but with a pretty neat factor ...
Taylor Fang's user avatar
0 votes
0 answers
25 views

Obtaining aggregate rotation and translation of 2D vector field (2d matrix of 2D motion vectors) produced from optical flow

I have the result of a dense optical flow in the form of 2D matrix of 2D motion vectors. I need to isolate the rotation and translation components of the motion to estimate camera rotation and ...
Alex Bausk's user avatar

1
2 3 4 5
72