{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
10
votes
1answer
202 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
72 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
80 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 & ...
0
votes
0answers
25 views
Kronecker sum matrix for a singular matrix pencil
The Kronecker sum of two matrices $A \in \mathbb{R^{n \times n}}$ and $B \in \mathbb{R^{m \times m}}$ is defined by the matrix.
$$A \oplus B = A \otimes I_m + I_n \otimes B \in \mathbb{R^{mn \...
2
votes
0answers
79 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
115 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
62 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
81 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
134 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 ...
4
votes
1answer
140 views
Is there a fast algorithm to test positivity of all principal minors of non-symmetric matrix?
I have a matrix $A \in \mathbb{R}^{n \times n}$ with positive eigenvalues. In the symmetric case, Sylvester's criterion implies that all the principal minors are positive. In the non-symmetric case, ...
5
votes
1answer
123 views
Numerical minimization spectral norm under diagonal similarity
This question is a follow up.
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(A) = \inf_{D} \lVert D^{-1} A D\...
1
vote
0answers
53 views
Calculation of $\chi^2$ for very small covariance matrices
I produced simulations of data for my experiments, changing each time my initial parameter $\theta$ , $n$ times: $\theta_1\, \theta_2, \cdots \theta_N$. For each realisation of my data I calculated ...
0
votes
0answers
29 views
Unstable convergence of a Poisson equation
What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
0
votes
1answer
222 views
Cholesky decomposition – non-positive definite matrix
In order to pass the Cholesky decomposition, I understand the matrix must be positive definite. However, I also see that there are issues sometimes when the eigenvalues become very small but negative ...
11
votes
0answers
165 views
Fast computation of matrix product $AXA^T$ with fixed $A$?
Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
0
votes
0answers
128 views
Smallest eigenvalue of a sparse matrix (updated)
Let $D_{1}$ be $(m-1)n \times mn$ matrix (that is, $(m-1)n$ rows and $mn$ columns) and $D_{2}$ be $m(n-1) \times mn$
defined as
$$\begin{cases}
D_{1}[(m-1)(j-1)+i ; m(j-1)+i] & = -1 , \\
D_{1}[(m-...
7
votes
1answer
187 views
Square root of a large sparse symmetric positive definite matrix
I am trying to calculate
$$Y = A^{\frac 12} X$$
where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
0
votes
0answers
45 views
Change of polynomial eigenvalues between polynomials
Given the polynomial eigenvalue problem
$$
p_t(z) = det ( P(z) + Q(t) ) = 0,
$$
where $P(z) = \sum_{i=0}^k P_i z^i$ with $P_i \in \mathbb{C}^{n \times n}$ and $Q(t) \in \mathbb{C}^{n \times n}$. The ...
1
vote
1answer
96 views
Compute the eigenvectors corresponding to the $k$ smallest eigenvalues w.r.t high dimensional symmetric sparse matrix?
So far as I know:
The power iteration method can only get the eigenvector corresponding to the largest eigenvalue;
The inverse power iteration method requires that the matrix is invertible;
The QR ...
2
votes
1answer
116 views
Efficient algorithm for solving a convex quadratic program [duplicate]
Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
4
votes
1answer
112 views
Solving a system of linear equations over the integers
I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.
...
3
votes
1answer
68 views
Numerical iterative methods for Poisson equation
Given a domain $\Omega \subset \Bbb R^n$ and $\Delta\varphi=f$ where $\varphi:\Bbb R^n \to \Bbb R$ is unknown and $f:\Omega\to \Bbb R$ is a blackbox function (for each $\bf x$ it provides $f({\bf x})$,...
2
votes
1answer
114 views
Quadratic matrix equation for $X\in \mathbb{C}^{ n\times p}$ with Hermitian parameters
Let $A\in \mathbb{C}^{ n\times n}$ and $B \in \mathbb{C}^{p \times p}$ be Hermitian matrices with $p < n$.
Find matrix $X$ such that $X^*AX=B.$
Solution in the case of positive definite $A$ and $...
7
votes
3answers
230 views
Checking positive semi-definiteness of integer matrix
Key Problem : Is there any theorem about eigenvalues or positive semi-definiteness of small size matrices with small integer elements?
I have to check positive semi-definiteness of many symmetric ...
1
vote
0answers
15 views
Empirical approaches to validate observational bounds on minimum gap between least eigenvalues of $n \times n$ correlation matrix and its submatrices
Let
$\Sigma$ be an $n \times n$ correlation matrix whose least eigenvalue is denoted by $\lambda$.
$\Sigma_i'$ be an $(n-1) \times (n-1)$ submatrix of $\Sigma$ obtained by eliminating the $...
2
votes
0answers
32 views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
7
votes
2answers
207 views
Linear equations with absolute values
Assume we have a set of equations in $x \in \mathbb{R}^n$
$$|a_i\cdot x|=b_i$$
where $a_i \in \mathbb{R}^n$ and $b_i>0$ are given.
Could such a system be solved efficiently?
In a theoretical ...
4
votes
0answers
125 views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
5
votes
1answer
330 views
In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?
In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to ...
4
votes
0answers
272 views
Generate non-negative linear combinations of non-negative vectors with different supports
(I will not be surprised if this problem has been solved and/or has a trivial solution – I just do not know the right terminology to google for it.)
So the problem is as follows. I have an $m \...
1
vote
0answers
42 views
smallest singular value over invertible sub-matrices
Consider the matrix $M = \begin{bmatrix} A & A B \end{bmatrix} \in R^{n \times (n+m)}$, with $A \in R^{n\times n}$, $B \in R^{n \times m}$, $m < n$, $m > 1$, $A$ symmetric positive definite.
...
0
votes
0answers
181 views
Conjecture about matrix systems of integer solution sets [duplicate]
Consider for all $i,j$ belong to $\Bbb N$ ; $a(i,j)=((2^{(i+1)}+1)^{(j-1)}+1)/2$,
then for all $n$ belong to $\Bbb N$ ; the solution set of the matrix system
$[a(i,j):1\leq i\leq n, 1\leq j\leq (1+...
1
vote
1answer
121 views
Laplace equation, medium discontinuity and finite difference method
The main question is: How to deal with the Poisson equation in the presence of the medium interface.
Let's say we have 1D Laplace equation:
\begin{equation}
-\frac{d}{dx}\left(\epsilon(x)\frac{d}{dx}\...
7
votes
0answers
142 views
A special eigenvalue problem
For my research I need to solve a generalised eigenvalue problem
$Ax=\lambda B x$, where $A$, $B$ are general matrices, and selectively find only eigen-pairs $\lambda, x$ such that $\lambda\in \mathbb{...
2
votes
0answers
30 views
Coarse grid correction
Let $A_h \in \mathbb{R}^{n \times n}$ be the matrix corresponding to a finite element discretization of some nonselfadjoint, bounded and indefinite bilinear form corresponding to a second order ...
4
votes
0answers
95 views
Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges
Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal).
If ...
1
vote
1answer
55 views
Solving Linear System with Noisy Input
I have the following triangular system
\begin{equation}
\begin{pmatrix}
1 & & & & \\
\mu_1 & 2 & & & \\
\mu_2 & \mu_1 & 3 & \\
\...
1
vote
0answers
376 views
What is the time complexity of the largest singular value and its vectors?
Full zero-error SVD on an $m \times n$ matrix $A$ would cost $O(\min(m^2n,mn^2))$. What is the time complexity if we need only the largest singular value and its corresponding vectors? I think it is $...
3
votes
1answer
194 views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
0
votes
0answers
498 views
Symmetric positive definite matrix with small condition number
When constructing a symmetric positive definite matrix $A$, it is desirable to have the condition number $\kappa(A)$ be as small as positive.
The question: is there a set of rules for matrix ...
1
vote
1answer
893 views
Is the square root of a matrix unique? [closed]
I know the answer is No, since you can put plus/minus on each eigenvalue. But how about putting a psd requirement? Like $A = S^2$, $S$ is psd, is $S$ unique?
I was worried about the case where if $\...
4
votes
0answers
343 views
Determining whether a Schur complement is invertible
Consider the symmetric matrix
$$M = \begin{bmatrix}
A & B \\
B^T & -C
\end{bmatrix}$$
where $A \in \cal{R}^{n \times n}$ and $C \in \cal{R}^{m\times m}$ are symmetric, ...
1
vote
0answers
224 views
Condition number of the product of two matrices
Consider two matrices $A$ and $B$ that are non-square in general and may not be full rank. Assuming their shapes are such that the product $A\cdot B$ is well-defined, what is the relationship between ...
3
votes
2answers
314 views
Lower bounds for the singular values of submatrices of othogonal matrices
Let $A$ be an $m \times n$ matrix, $m\geq n$, and let $A=U\Sigma V^T$ be its singular value decomposition.
Let us partition $A$ as $A=(A_1|A_2)$, where $A_1$ is of size $m \times k$, and all columns ...
1
vote
1answer
90 views
error bound for least square minimization
Let $X = [x_1 \cdots x_N] \in \mathbb{R}^{d \times N}$ and $ T= [t_1 \cdots t_N] \in \mathbb{R}^{1 \times N}$. Define
$$
E(w) = \text{tr}(T - w^TX)(T - w^TX)^T
$$
as least square energy. When ...
0
votes
1answer
101 views
How to show inconsistency of a linear system of equations? [closed]
Consider the (real) linear system of equations $A\mathbf{x}=\mathbf{c}$ of size $N$ as
$$
\begin{bmatrix} a_{N}-a_{2}& a_{2}& 0 &\dots& 0 & -a_{N} \\-a_{1} & a_{1}-a_{3}&a_{...
3
votes
2answers
175 views
Question about preconditioning
I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here.
I understand that for many iterative methods, convergence rates can be shown ...
3
votes
3answers
338 views
Is this inequality involving the Frobenius norm right?
Let $A$ be a generic (or varying) square, real $ n \times n$ matrix. Let $G$ be a fixed $n \times k$ matrix, $k < n.$ Denote by $||.||_F$ the Frobenius norm.
Is it true that $||AG||_F \geq c(G) ||...
8
votes
1answer
273 views
When are two binary matrices simultaneously equivalent to their transpose?
For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $...
7
votes
2answers
857 views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
