Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

2
votes
0answers
63 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 ...
5
votes
1answer
104 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
52 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
64 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
128 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
131 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
118 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
27 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
137 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 ...
10
votes
0answers
150 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
124 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
168 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
81 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
108 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. ...
2
votes
1answer
63 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
106 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
211 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
186 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
124 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
298 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
139 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
40 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
177 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
118 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
139 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
29 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
93 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
53 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
325 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
172 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
418 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
738 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
336 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
195 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
264 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
86 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
100 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
174 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
328 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
271 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
793 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 ...
4
votes
1answer
163 views

minimizing the product of rayleigh quotient

The problem is: $$\min_{\alpha}\frac{\alpha^T A \alpha}{\alpha^T\alpha}\frac{ \alpha^T B \alpha}{\alpha^T\alpha}$$ where $A$ and $B$ are symmetric and positive definite matrix. I think the explicit ...
3
votes
1answer
214 views

Properties of one dimensional null space

Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition). Let $S: \...
3
votes
2answers
550 views

Matrix equation with Hadamard product and its own inverse involved

I know there is an almost exactly same question here but I have further specifications. So my problem is as follows: $$ \Omega^{-1}=\dfrac{1}{n}\left(\Omega\odot \mathbf{W}+\mathbf{X}'\mathbf{X}+\...
0
votes
1answer
299 views

Recurrence Equation and Matrix Convergence

To begin with, let us give the conceptual background needed to expose the problem. First of all, we shall consider the set $\mathbb{L}^{n} = \mathbb{R}^{n}_{\geq0} = \{\overrightarrow{x}\in\mathbb{R}^{...