# Questions tagged [numerical-linear-algebra]

{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

195
questions

**0**

votes

**0**answers

13 views

### Compute Frobenius inner product of two tensor-trains in terms of tensor contractions

Let $p\in\mathbb N$, $n\in\mathbb N^p$ and identify the Hilbert space tensor $\bigotimes_{k=1}^p\mathbb R^{n_k}$ with $\mathbb R^{n_1\times\cdots\times n_p}$ (equipped with the Euclidean inner product)...

**1**

vote

**0**answers

68 views

### Computational complexity in linear solvers [migrated]

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain ...

**1**

vote

**0**answers

14 views

### Show that a tensor-train is contained in a recursive sequence of subspaces

Let
$p\in\mathbb N$;
$n_k\in\mathbb N$ and $\left(e^{(k)}_1,\ldots,e^{(k)}_{n_k}\right)$ denote the standard basis of $\mathbb R^{n_k}$ for $k\in\{1,\ldots,p\}$;
$u\in\bigotimes_{k=1}^p\mathbb R^{n_k}...

**0**

votes

**0**answers

19 views

### Most efficient way to solve against large sparse matrix with a few dense rows and columns?

I have a constrained optimization problem of the form:
$$
\min_{Bx=g} \frac{1}{2} x^T A x - x^T f
$$
$A \in \mathbb{R}^{n\times n}$ is positive semi-definite (with a tiny null space of dimension &...

**1**

vote

**1**answer

42 views

### How can I find minimum and maximum eigenvalue of non-positive define matrix [closed]

There is a power iteration method, but it only returns the greatest(in absolute value) eigenvalue of matrix. So when we have negative eigenvalues it'll give wrong results.
Is there any method, which ...

**0**

votes

**0**answers

66 views

### How to solve a non-local self-consistent equation

I have been struggling lately with solving numerically an equation of the form:
$$ g(x\pm x_{0}) = F[ g(x) ] $$
where $g(x)$ is a matrix satisfying the condition $g(x\to\pm\infty)=0$. My question is ...

**1**

vote

**0**answers

12 views

### One-sided Jacobi SVD and Divide&Conquer SVD stability and cost [closed]

I'm studying SVD, in particularly the Jacobi SVD and Divide&Conquer SVD algorithms. I can't find anything on the stability and error analysis on these methods. Also can someone show show me what's ...

**0**

votes

**0**answers

26 views

### ADMM for solving linear systems

I would like to use ADMM for solving $Mx=b$, where $M\in \mathbb{R}^{R\times R}$ is symmetric and positive definite. I know that a lot of methods will do for me in this case, but I'm specially ...

**2**

votes

**1**answer

56 views

### How to find the elliptical arc that corresponds to the cubic bezier curve

Let's assume I have a cubic bezier curve that is provided with A, B, C, D points, where
A is the start of the curve
B is the first control point
C is the second control point
D is the end of the ...

**0**

votes

**0**answers

34 views

### Orthogonality condition of symmetric matrix pencil

Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...

**0**

votes

**0**answers

11 views

### Update rank-revealing factorization after applying $I \otimes $(small matrix)

Suppose one knows an $(m, n)$ matrix $A$ along with some rank-revealing factorization (let's say the economy SVD for conreteness), $A = U S V^H$, with $S$ an $(r, r)$ matrix where $r$ is the numerical ...

**6**

votes

**1**answer

84 views

### Numerical method for simultaneous computation of eigenvalues of a family of commuting matrices

I have a problem where I have $n$ commuting matrices $M_1,\dots,M_n$. It is a well-known fact that commuting matrices are simultaneously diagonalizable/triangularizable. I need to find the eigenvalues ...

**0**

votes

**0**answers

44 views

### Diagonal and orthogonal minimization of spectral norm

This question is a follow up with an extra orthogonal matrix.
Let $A$ be a real square matrix of size $n \times n$. How to determine the minimum spectral norm under diagonal similarity, i.e.,
$$
s(...

**7**

votes

**1**answer

146 views

### Minimize spectral radius with orthogonal matrix

Let $A$ be a real square and invertible matrix. I would like to find
$$
s(A) = \min_U \rho(U A),
$$
Where $U$ is orthogoal, i.e. $U U^T = I$ and $\rho(A)$ is the spectral radius, i.e. the largest ...

**4**

votes

**1**answer

118 views

### How to obtain the rational solution of a linear system efficiently? [closed]

Suppose that I have a linear system $AX=b$ with $A\in\mathbb{Z}^{n\times m}$ and $b\in\mathbb{Z}^{n}$. Assume that $AX=b$ has exactly one rational solution. Then how can I obtain this solution ...

**2**

votes

**1**answer

41 views

### Matrix factorization for dimensional reduction similar to spectral decomposition/SVD

I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \...

**3**

votes

**0**answers

148 views

### Matrix equations motivated by generalization of $QR$ decomposition

The following problem is motivated by considering a certain generalization of the $QR$ decomposition of a matrix.
Let $A, B \in M_n(\mathbb{R})$.
(i) Can we always find $Q_1, Q_2 \in M_n(\mathbb{R})...

**1**

vote

**1**answer

128 views

### Action of square root of tridiagonal matrix product on vector

Assume nonsymmetric, tridiagonal matrices $A, B \in \mathbb{R}^{n\times n}$ (where $n$ is in the order of 1000) and $A, B, AB$ are diagonalizable and have positive eigenvalues.
How do you efficiently ...

**0**

votes

**0**answers

19 views

### Obtain a sparse solution for a bad conditioned linear system with either or constraints

What is the best way to obtain a sparse solution for a linear system $\mathbf{A}\vec{x}=\vec{b}$ with $x_n \in \mathbb{R}$? The linear system is special, because I know that:
some columns $\vec{c}_n$ ...

**2**

votes

**0**answers

72 views

### Sparse perturbation

Let $x, x_0\in\mathbb{R}^n$ be two vectors satisfying $$\frac{||x||_1}{||x||_2}\leq\frac{||x_0||_1}{||x_0||_2}.$$
$|| \cdot||_1$ and $|| \cdot||_2$ are the $\ell_1$ and $\ell_2$ norm in $\mathbb{R}^n$,...

**2**

votes

**1**answer

284 views

### Minimise $\sum_i \begin{Vmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{Vmatrix}$

Consider column vectors $\boldsymbol{z}_i$, $\quad i=1,\dots,n$.
Each $\boldsymbol{z}_i$ has $j$ elements and can be expressed as $\boldsymbol{z}_i = \begin{bmatrix} \boldsymbol{x}_i \\ \boldsymbol{y}...

**10**

votes

**1**answer

401 views

### Solving $AXB + X\odot C = D$

I need to solve the following equation for $X$ with $d$-by-$d$ matrices $A,B,C,D$ and Hadamard product $\odot$
$$AXB + X\odot C = D$$
Vectorizing all terms gives a solution with $O(d^6)$ complexity, ...

**2**

votes

**0**answers

38 views

### Large-scale projected minimum-eigenvalue computations

I am interested in efficient numerical procedures for solving large-scale instances of the following projected minimum-eigenvalue problem:
$$\mu := \min_{v \in \mbox{ker}(A)} \frac{v^T H v}{\lVert v \...

**1**

vote

**0**answers

24 views

### Discrete maximum priniciple for parabolic operators

While reading a paper on the topic 'Numerical solutions for generalized Black-Scholes equation', It is given that their numerical scheme can be executed explicitly by solving a linear system $\mathbf ...

**6**

votes

**0**answers

96 views

### Algorithm to check a conjectural value for the rank of a large matrix

Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:
I'm checking a conjecture which at the end of the day boils down to the ...

**4**

votes

**1**answer

125 views

### Row-based iterative algorithms for computing the kernel of a matrix

Suppose $A$ is an $m \times n$ matrix in the form
$$A=\begin{pmatrix} — a_1 —\\ — a_2 —\\ \vdots \\ — a_m — \end{pmatrix}$$
where $a_i \in R^n$ is the $i$-th row of $A$. I know that it is possible ...

**1**

vote

**0**answers

180 views

### Effective Jordan normal form

Given $A \in \mathrm{GL}_m(\mathbb{C})$, I can conjugate it by some $B \in \mathrm{GL}_m(\mathbb{C})$ into its Jordan normal form. That is, for some $n\le m$, there exists a $J \in \mathrm{GL}_n(\...

**2**

votes

**1**answer

246 views

### Is it faster to compute eigenvalues or coefficients of characteristic polynomials?

Given $A \in \mathsf{M}_n(\mathbb{C})$ (no special structure) is it (generally) faster to compute its eigenvalues or the coefficients of its characteristic polynomial?
References/insights would be ...

**5**

votes

**1**answer

209 views

### Best orthogonal approximation of rank 1 matrix

Let $X=\lambda_0u_0v_0^T\in\mathbb{R}^{n\times n}$ be a rank 1 matrix where $\lambda_0\in\mathbb{R}$, $u_0,v_0$ are of unit Euclidean norm. What is the solution of the following problem?
$$\hat{X}=\...

**2**

votes

**2**answers

149 views

### Parametrising a sparse orthogonal matrix

I need to find a way to parametrise a matrix that is both sparse (to some degree) and orthogonal, i.e., I am looking for a parametrisation that describes $A \in \mathbb{R}^{n\times m}$ such that $AA^𝑇...

**0**

votes

**0**answers

69 views

### Matrix decomposition in a specific form

Can we prove that for any real valued $d\times d$ matrix $A$, $A$ can be decomposed to finite product of such matrices
$$A=\prod_{i=1}^n (I+R_i)$$
where $I$ is the identity matrix and $\operatorname{...

**5**

votes

**1**answer

126 views

### Finite difference for a highly nonlinear equation - The wind within the forest

Based on the Navier-Stokes equations and a few parameterizations, the horizontal steady-state wind $u(z)$ within a forest of height $H$ satisfies:
$$
a\Big(\frac{du}{dz}\Big)^{\!2} + b\frac{du}{dz} \...

**2**

votes

**2**answers

174 views

### Methods of solving linear system of equations, how to select the appropriate method

A linear system of equations Ax=b can be solved using various methods, namely, inverse method, Gauss/Gauss-Jordan elimination, LU factorization, EVD (Eigenvalue Decomposition), and SVD (Singular Value ...

**1**

vote

**0**answers

70 views

### L1 Norm regression [closed]

First time poster...apologies for formatting.
I am trying to devise a solution to a familiar linear algebra equation, Ax=b, where all elements in A are non-negative and all the elements in b are ...

**1**

vote

**0**answers

62 views

### How to compress variables in a linear regression

I have a large linear regression where all the independent variables are logical (ie TRUE/FALSE) and sparse. The data has roughly 10,000 variables and 10 million observations, on average around 20 ...

**1**

vote

**0**answers

101 views

### Why de-blurring a blurred image is an ill-conditioned problem? [closed]

Why de-blurring a blurred image is an ill-conditioned problem? What's the intuitive explanation? How to show it using the condition number?

**4**

votes

**0**answers

68 views

### Is there a fast way to compute the lowest eigenvalue of this symmetric PD matrix in this specific scenario?

Consider
$$C = A^H D A + M$$
where
$A$ is a $m \times m$ unitary matrix.
$D$ is a $m \times m$ diagonal matrix with entries either $0$ or $1$.
The number of $1$'s is $n \ll m$.
$M$ is a $m \times ...

**1**

vote

**1**answer

162 views

### Sparse, left-looking LU factorization

I'm trying to understand the left-looking LU factorization algorithm for sparse matrices, by reading T.A. Davis' book, and have trouble in one step (sorry for the specific question) about returning ...

**2**

votes

**1**answer

86 views

### why there is no relaxation method for Jacobi linear system iterative methods?

I found that the relaxation methods for solving linear system as an iterative sequence are derived from the Gauss-Seidel method and not from the Jacobi method. I understand that the Gauss-Seidel ...

**0**

votes

**1**answer

179 views

### Sparse dense matrix versus non-sparse dense matrix in eigenvalue computation

I have a matrix in the form of $2n\times 2n$ block matrix
$$
A = \begin{pmatrix}O& W\\
J& D\end{pmatrix}
$$
where, $O$ is an $n\times n$ zero-matrix; $W$ is a n-by-n diagonal matrix, $W = ...

**2**

votes

**1**answer

349 views

### Eigenvalue and Eigenmatrix of a 3D Tensor - How to calculate it?

How to calculate easily the eigenmatrix of a 3D tensor.
I try immersing the tensor in a big matrix, in my case, the tensor is of nxnxn and I can build an n^2 x n^2 matrix that contains all the "...

**4**

votes

**1**answer

82 views

### Numerical instability of the axis-angle representation of rotations in 3D

Suppose that I have $1000$ pair of points where each pair consists of a point in $\mathbb{R}^3$ and its image after a rotation in $\mathrm{SO}(3)$ with some noise. I have used RANSAC to find the ...

**11**

votes

**1**answer

424 views

### Decide if a matrix is transposable

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations.
Is there an efficient a way/algorithm to decide if a given matrix is
...

**1**

vote

**1**answer

316 views

### Closed Form Solution for Optimization Problem over the Space of Rigid Transforms

Is there a closed form solution to this constrained optimization problem:
\begin{equation}
\min_{R \in SO(3),\, \mathbf t \in \mathbb R^3} = \sum_{i = 1}^N \| M_i(R \mathbf p_i + \mathbf t) \|^2,
\...

**0**

votes

**1**answer

98 views

### Matrix equation of the form $C A C^\intercal = D$

Consider the following square matrix
\begin{align}
A = \left(\matrix{d & 0 & -\frac12 & 0 & 0 & 0 & 0 & 0 \\
0 & d & -d+1 & -\frac12 & 0 & ...

**2**

votes

**0**answers

127 views

### An inequality concerning the solution of a Lyapunov equation

Let $A$ be an Hurwitz stable matrix (i.e. the real part of the eigenvalues of $A$ lie in the left-half plane) and $Q$ be a positive semidefinite matrix ($Q\ge 0$, for short). Let $P>0$ be the ...

**6**

votes

**1**answer

126 views

### Any convergence rule for ${\mathbf X}_k={\mathbf A}{\mathbf X}_{k-1}{\mathbf B}$?

We know iteration ${\mathbf X}_k=\mathbf{A}{\mathbf X}_{k-1}$ converges if the spectral radius of $\mathbf A$ is smaller than 1 (see here). Is there any known rule for iteration ${\mathbf X}_k={\...

**0**

votes

**1**answer

157 views

### Computing spectrum of convex combination of SPD matrices given individual spectral decompositions

Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K_{i}\right\} _{i=1}^{M}, U_{i}D_{i}U_{i}^{T}=K_{i},\quad i=1,\dots,M,$$ ...

**1**

vote

**1**answer

594 views

### Lanczos algorithm for finding $k$ smallest eigenvector

I am trying (and have been recommended) to use the Lanczos algorithm to find the $k$ smallest eigenvectors. However, all of the literature seems to talk about this algorithm as a way to estimate the $...

**7**

votes

**1**answer

179 views

### Is there any sort of higher-order SVD (quadratic and above) for dimensionality reduction?

(Posted this on math.stackexchange and cross.correlated over more than a week ago, but didn't get an answer, and this is a question in my research so this seems like it might have been the better ...