All Questions
Tagged with linear-algebra numerical-linear-algebra
195 questions
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
3
votes
1
answer
143
views
A problem about matrix inverse and regularization methods
I'm researching the problem of solving the equation $A\mathbf{x}=\mathbf{b}$ with ill-conditioned matrices. We know that if we solve it directly, like $\mathbf{x}=\mathrm{inv}(A)\ast\mathbf{b}$, then ...
- 33
0
votes
0
answers
96
views
When can a point be reconstructed from relative angle measurements?
Given a set of points $p_1,\dots,p_n$ in $\mathbb{R}^d$ and a target point $x\in\mathbb{R}^d$, I measure all the angles between all pairs of points and the target point. In other words, I have the ...
- 427
2
votes
1
answer
122
views
Is it possible to solve this kind of quadratic simultaneous equations?
$$\mathbf{x} = (x_1, x_2, ..., x_N)^T \in \mathbb{R}^{N} \\
\mathbf{A}_i \in \mathbb{R}^{N \times N},
\mathbf{b}_i \in \mathbb{R}^N ,
\mathbf{c}_i \in \mathbb{R}\\
\mathbf{x}^T\mathbf{A}_i\mathbf{x}...
- 23
2
votes
0
answers
67
views
Characteristics of conjugate gradients' iterations for a matrix with clustered spectrum
I am interested in solving
\begin{equation}
Ax = b
\end{equation}
for a large sparse linear symmetric positive definite matrix $A$ by Conjugate Gradients method. (These systems usually come as ...
- 121
4
votes
1
answer
342
views
rank of an integer valued matrix
I make some numerical experiments, involving rank of integer valued matrices of the size about $14\times 24$. As the matrix is integer valued, theoretically there should be no room for errors. However ...
- 728
1
vote
1
answer
297
views
Nearest Kronecker product to sum of Kronecker products
I am interested in efficiently finding the closest Kronecker decomposition to the sum of $k$ Kronecker products:
$$\min_{A,B} || A \otimes B - \sum_{i=1}^k A_i \otimes B_i ||_F$$
where $A,A_i$ are $p \...
- 111
1
vote
0
answers
95
views
Vandermonde-type factorization of moment matrix?
Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...
- 275
0
votes
0
answers
67
views
Concentration of bilinear forms
This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
- 6,962
0
votes
1
answer
91
views
Matrix quantization and effect on singular values
Let $A$ and $B$ be an $N\times n$ matrix with $n\le N$, and let $\sigma_1(X),\dots \sigma_n(X)$ denote the singular values of $X\in \{A,B\}$. Do we have upper and lower bounds for
$$
\|
\sigma_i(A)-\...
- 5,405
0
votes
0
answers
28
views
The selection of minimal generating sets in Lie algebra
Suppose $A$ is a Lie algebra on field $F_{p}$ with $[A,A,A]=0$. Denote $\{a_{1},\cdots,a_{d}\}$ is a minimal generating set of $A$.It's possible that $[a_{i},a_{j}]=0$ for some $1\leq i<j\leq d$ ...
- 171
7
votes
1
answer
307
views
Efficiently solve the Sylvester equation $AX+XA = C$ where $X$ is skew-symmetric
Is there a way (more efficient than the standard vectorization) to solve the following Sylvester equation in the skew-symmetric matrix $X$ $$AX+XA = C$$ where the matrix $A$ is symmetric positive ...
- 173
2
votes
2
answers
235
views
Theoretical/Practical Implications of DFT Eigenvectors
Discrete Fourier transform (DFT) has only four distinct eigenvalues: $±1$ and $±i$. For large matrices , each eigenvalue $λ$ yields a multidimensional eigenspace, allowing linear combinations of ...
- 4,058
3
votes
1
answer
273
views
Inflection point calculation for cubic Bézier curve encounters division by zero
I've been working on finding the inflection points of a cubic Bezier curve using the method described in a paper Hain, Venkat, Racherla, and Langan - Fast, Precise Flattening of Cubic Bézier Segment ...
- 133
2
votes
1
answer
217
views
How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?
Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^...
- 21
0
votes
2
answers
131
views
Reshaping data vector into a matrix for deconvolution using a circulant matrix
Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means ...
- 879
5
votes
0
answers
202
views
Difficulty of solving $Ax=b$ in terms of limiting spectral density of $A$?
Suppose $A$ is a random real-valued $n\times n$ matrix and we want to know the difficulty of solving $Ax=b$ when entries of $b$ are sampled IID from Normal$(0,1)$.
Can we say anything about the ...
- 2,442
0
votes
0
answers
99
views
Efficient method to determine minimum eigenvalue of $2 \times 2$ block diagonal matrix
Suppose $H$ is a $2 \times 2$ block-diagonal symmetric matrix in $\mathbb{R}^{2^N \times 2^N} $. That is
$$ H = \begin{pmatrix} A_1 & 0 & \cdots & 0\\ 0 & A_2 & \cdots & 0 \\
...
- 131
1
vote
0
answers
329
views
The geometrical multiplicity of the nilpotent matrices
The following point is well-known in the literature.
Theorem. Let $A$ be a non-negative matrix in $M_n(\mathbb{R})$. If $A$ is nil-potent, there is a permutation matrix $P$ such that $P^tAP$ is ...
- 4,058
1
vote
0
answers
179
views
QR algorithm for eigenvalues and eigenvectors of large symmetric matrices
I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift ...
34
votes
3
answers
3k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
- 777
3
votes
0
answers
259
views
Efficient way to calculate Smith Normal Form of large integer matrices
I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...
1
vote
0
answers
138
views
Generalized eigenvalues of block matrix
Let $A, D \in \mathbb{R}^{n\times n}$ be symmetric matrices and consider the following matrix pencil
$$
\begin{pmatrix}
-I & A+\lambda I \\
A+\lambda I & -D \\
\end{pmatrix}
$$
If we already ...
- 205
3
votes
0
answers
378
views
efficient numerical algorithm for matrix determinant
It appears that in numerical analysis the question of computing the determinant $\det A$ of a real or a complex $n\times n$ matrix $A$ is not well-studied, and a usual recommendation is to use matrix ...
- 14k
3
votes
1
answer
368
views
Linear system with sum of Kronecker products
Here and here, specific ways to address the equation in $x$, for $N=2$, are given:
$$\sum_{i=1}^N (A_i\otimes B_i)x=c$$
Is anything know about the case $N>2$?
I am looking in fact for an efficient ...
- 235
30
votes
2
answers
1k
views
Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?
I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \...
- 4,943
3
votes
1
answer
181
views
The proof of the invertibility of $\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$
Suppose that $n$ is even. Any suggestion/appraoch to prove that $S=\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$ is invertible?
- 4,058
3
votes
1
answer
370
views
The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$
What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ when $n$ is odd?
- 4,058
3
votes
0
answers
173
views
Can the Jordan decomposition of a matrix be computed in a backwards stable way?
Let $PJP^{-1}$ denote the Jordan decomposition of $M$. The matrix $J$ is a direct sum of Jordan blocks; it is unique up to permutation of the Jordan blocks. The matrix $P$ is not unique.
There are two ...
- 4,943
0
votes
0
answers
232
views
How to analyse the range of eigenvalues of a symmetric and indefinite matrix?
Let $G$ be a symmetric and indefinite matrix defined as follows
$$ G := S - \begin{pmatrix} I_n & I_n \\ I_n & I_n \end{pmatrix},$$
where $S$ is a symmetric positive definite matrix of size $...
- 1
0
votes
1
answer
74
views
$\det(HH’) = 0$ for nonnegative $H$
$H$ is an $n\times m$ matrix with non-negative coefficients and $n < m$. $H'$ is the transpose of $H$.
Are the following statements true?
If $\det(HH’) > 0$, the rows of $H$ define the edges of ...
- 13
1
vote
1
answer
68
views
Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?
I asked the same on math.Stackexchange.
I have $n$ (say $n = 300$) vectors $v_1,\dots,v_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v_j$ I denote it's coordinates as $v_{j1},\...
- 1,048
1
vote
0
answers
38
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
- 11
3
votes
0
answers
122
views
Preconditioners for $Ax=y$ that rely on hierarchical statistical modeling
Solving $Ax=y$ exactly can be done as:
fit a linear autoregressive model by treating rows of $A$ as data
apply this model to $A^T y$
Imperfect predictive model corresponds to an approximate inverse ...
- 2,442
1
vote
1
answer
59
views
Does norm of discrepancy decrease monotonously in CGLS/CGNR
I am the author of the package for tomographic reconstruction https://github.com/kulvait/KCT_cbct I have implemented CGLS/CGNR , algorithm which applies conjugate gradients on normal equation
$$
A^\...
- 151
7
votes
2
answers
244
views
Finding $\theta$ such that at least one eigenvalue of $A(\theta)$ is real
Is there a known method to find a set of $\theta$ such that at least one eigenvalue of $A(\theta)$ is purely real?
Assume $A(\theta)$ is a real square matrix whose elements are linear functions of a ...
- 433
2
votes
2
answers
243
views
Sum over exponentiated bilinear form in finite-field vector space
Let $A$ be a linear map over the finite-field vector space $(\mathbb F_2)^n$, i.e., an $\mathbb F_2$-valued $n\times n$ matrix, not necessarily symmetric. I'm interested in the sum
$$Z(A) = \sum_{X\...
- 3,001
2
votes
0
answers
121
views
Proving some properties of the Landweber–Fridman iterates
$\newcommand\norm[1]{\lVert#1\rVert}$Let $B\in \mathbb R^{n\times n}$ be a symmetric and positive definite matrix. Assume that $x\in \mathbb R^n$ is the solution of $Bx=w$ for some given $w\in \mathbb ...
- 21
1
vote
0
answers
274
views
Find the eigenvectors from the QR algorithm in the unsymmetric case
It is possible to find many references describing the QR Algorithm with more or less refinements to approximate the eigenvalues of a square matrix $A\in\mathbb{R}^{n\times n}$.
I implemented a version ...
- 11
1
vote
0
answers
198
views
Complexity of singular value decomposition using matrix multiplication oracles
Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. ...
- 662
0
votes
1
answer
397
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
- 1
0
votes
1
answer
118
views
Proving maximum value of a determinant of $I - B$, where $B$ is nonnegative matrix
I have the following setting:
Let $0 \leq r < 1$ and let $\{z_i\}_{i=1}^k$ be $k$ complex numbers such that $|z_i| \leq r$ for all $i$.
Moreover, $r + \sum_{i=1}^k 2Re(z_i) \geq 0$
I am interested ...
- 59
3
votes
2
answers
2k
views
Iterative methods for linear system with non-diagonally dominant matrix
I have a linear system
\begin{align*}
\left[\begin{array}{cccc}
1 & 2 & 1 & -1 \\
3 & 2 & 4 & 4 \\
4 & 4 & 3 & 4 \\
2 & 0 &...
- 65
1
vote
1
answer
223
views
Does Wilkinson's shift need to be discontinuous?
Given a symmetric Hessenberg matrix $A = \left[\begin{matrix}\ddots& \vdots & \vdots\\\dotsb & a & b\\\dotsb& b & c\end{matrix}\right]$, the Wilkinson shift $\mu$ employed in ...
- 4,943
5
votes
1
answer
251
views
Smooth, non-analytic functions of non-normal matrices
My apologies if this isn't a well-enough-posed question, I think I'm partly unsure of what exact question to even ask.
There are many different ways in which we can take a function of a matrix.
We ...
- 854
3
votes
0
answers
147
views
Convolution integral and its matrix representation
My background is chemistry and I was exploring some one dimensional deconvolution problems i.e., resolution of two or more overlapping peaks. A lot of excellent work was done in the 1970-80s. However, ...
- 879
2
votes
0
answers
194
views
Maximize the product of Hadamard matrix and a vector
Let $X$ be an $n \times n$ Hadamard matrix (i.e. entries are in $\{-1,1\}$ and rows are orthogonal). For my application, we can assume $n=2^k$.
Given a vector $\bf{w} \in R^n$, I want to find the $X^*$...
- 21
0
votes
0
answers
227
views
Decomposition of symmetric block matrix
I came across this question and got really interested about it. There, the OP asks whether is possible to decompose a $2n \times 2n$ block matrix:
$$ \begin{pmatrix}
X & I \\
I & Y
\end{...
0
votes
1
answer
266
views
Using QR or SVD to sum up finite number of matrices
Problem
I was wondering if there are any theoretical results that tackle the following problem:
Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\...
3
votes
1
answer
439
views
Derivative of eigenvalues of a symmetric tridiagonal matrix built via the Lanczos-Arnoldi scheme
Suppose $\mathbf{A}(\mu)$ being a symmetric positive definite matrix of dimension $n$ where its elements depend parametrically on the real parameter $\mu$.
Suppose now to build the orthonormal basis ...
- 131