Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
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 ...