Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
195
questions
0
votes
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...
