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

**0**

votes

**0**answers

21 views

### Non symmetric, zero column sum, positive diagonal and negative off diagonal entries matrix bound?

Under which conditions can the A-inner product of a non symmetric, zero column sum, positive diagonal and negative off diagonal entries matrix be bounded by the L2-inner product?
$A \in \mathbb{R}^{n ...

**1**

vote

**0**answers

27 views

### Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...

**2**

votes

**0**answers

18 views

### Computing 3-term Connection Coefficients for Wavelets

I am trying to calculate the three-term connection coefficients
$$
Λ_{l,m}^{d_1,d_2,d_3} = ∫_{-∞}^∞ φ^{(d_1)}(x) φ^{(d_2)}_l(x) φ^{(d_3)}_m(x) dx
$$
for Daubechies wavelets numerically using Python. ...

**1**

vote

**0**answers

48 views

### Matrix exponential bounds

Let $A$ be a stochastic matrix, $q\in (0,1)$. How to bound $n$ such that $$q^n A^n e^A \leq e^A$$
Note that here $e^A$ is the matrix exponential, and $\leq$ is taken entrywise.
To be clear, what I ...

**3**

votes

**1**answer

143 views

### The spectral norm of the truncated exponential of a matrix

Let $A$ be a matrix satisfying $A^*+A\leq0$, it can be shown that $\|e^{tA}\|_2\leq1$ for all $t\geq 0$, where $\|\cdot\|_2$ is the spectral norm defined as largest singular value of the matrix.
I am ...

**1**

vote

**1**answer

52 views

### How to retrieve eigenvectors from shifted QR algorithm?

I understand that the key to retrieve eigenvectors in the non-shifted QR algorithm is to accumulate the transformations at each steps in the following way:
$Q = \Pi_i Q_i$
Can we accumulate the ...

**0**

votes

**0**answers

81 views

### Orthogonal Procrustes problem for sub-spaces?

By Orthogonal Procrustes problem I mean given matrix $A$ and $B$ finding a orthogonal matrix $R$ which most closely maps $A$ to $B$, this has a solution as shown in https://en.wikipedia.org/wiki/...

**3**

votes

**0**answers

91 views

### Finding nearest Toeplitz matrix to a given matrix

For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...

**4**

votes

**1**answer

102 views

### Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...

**7**

votes

**2**answers

2k views

### Finding the smallest eigenvalues of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $M$. $M$ is a Laplacian matrix, and it has the following structure: $...

**0**

votes

**0**answers

25 views

### Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...

**28**

votes

**9**answers

12k views

### Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...

**7**

votes

**2**answers

240 views

### How to estimate a specific infinite matrix sum

Let $M$ be an $n$ by $n$ matrix with each diagonal element equal to $k$ and each non-diagonal element equal to $k-1$ where $n$ and $k$ are positive integers. Let $k < n$ and we can assume both $k$ ...

**1**

vote

**0**answers

40 views

### The application of recursive SVD [closed]

Given an n*m matrix A, the SVD decomposition of A is ${\rm SVD}(A)$= $USV^t$.
The application of SVD to the product of U and S gives as a result the same matrices multiplied by the identity matrix, i....

**2**

votes

**0**answers

66 views

### SVD when only off-diagonal terms are known

I have a real matrix $A \in \mathbb{R}^{n\times n}$ such that:
$A$ is symmetric
All the off-diagonal terms are known and positive
Has rank $k<n$
Unfortunately I don't know the values of the ...

**5**

votes

**0**answers

81 views

### Tensor matricizations and their decompositions

Suppose we have a 4-index tensor $t_{ijkl}$ (all 4 dimensions are equal size). We can make a matrix out of it by taking first and last two indexes as new indexes: $t_{ijkl} \rightarrow M_{ij, kl}$. ...

**0**

votes

**1**answer

81 views

### Need help with computational and numerical methods for solve equations

This is my first question on this community. I am a applied scientist, not a mathematician.
I have the following simplified problem:
Let $u: [0,1] \rightarrow \mathbb{R}_+$ a real valued function ...

**1**

vote

**1**answer

33 views

### Similarity transform of a diagonalizable matrix that minimizes the Euclidean condition number

If I have a diagonalizable matrix $A = V\Lambda V^{-1}$, is there a way to show that for any similar $B$ such that $B = T\Lambda T^{-1}$, the Euclidean condition number $\kappa_2(B) \geq \kappa_2(\...

**7**

votes

**1**answer

82 views

### Add a multiple of $I$ to a matrix to minimize its operator norm

Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...

**8**

votes

**1**answer

265 views

### Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?

How can I efficiently compute
$\mathrm{trace}(A(B^{-1}))$
where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-...

**10**

votes

**2**answers

288 views

### Why Householder reflection is better than Givens rotation in dense linear algebra?

It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...

**0**

votes

**0**answers

71 views

### Simplifying product of matrix exponential?

Is there a known generalization for n-term matrix exponential multiplication?
I am aware that the Baker–Campbell–Hausdorff formula could be used, e.g.:
...

**0**

votes

**1**answer

56 views

### Is spectral properties a general term for condition number?

I am reading an article about solving large sparse linear systems, in this paper it’s said that most of the iterative methods to solve $Ax = b$ are very much influenced by the spectral properties of ...

**6**

votes

**2**answers

265 views

### A system of non-linear equations that is decomposable as a product — uniqueness of solution?

I have a system of non-linear equations
$ a_1=f_0 g_1$
$a_2=f_1 g_1 + f_0 g_2$
$a_3=f_2 g_1 + f_6 g_2 + f_0 g_3 $
$a_4=f_3 g_1 + f_7 g_2 + f_6 g_3 + f_0 g_4 $
$a_5=f_4 g_1 + f_8 g_2 + f_7 g_3 + ...

**7**

votes

**2**answers

2k views

### efficient rank-two updates of an eigenvalue decomposition (or more genearlly SVD)

Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al. and Bunch, et al. have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...

**5**

votes

**2**answers

842 views

### Linearly constrained eigenvalue problem

Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& \...

**0**

votes

**2**answers

72 views

### Solving sparse linear least squares or a positive definite 5-band matrix system fast

I want to quickly solve linear least squares problem for $x \in \mathbb{R}^n$
$$min_x \left\| A x - b \right\|_2^2$$
with a special sparse structure where each row in $A$ has only up to 4 ...

**1**

vote

**2**answers

438 views

### Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...

**6**

votes

**3**answers

123 views

### Algorithm to quickly compute the individual inverses of a linear sequence of matrices

Fix $n \times n$ real symmetric positive definite matrices $A$ and $B$. Fix vectors $x$ and $y$ in $\mathbf{R}^n$. I want to compute the following bilinear products quickly: $\{x^T (A+mB)^{-1} y\}_{m=...

**3**

votes

**0**answers

110 views

### Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e.,...

**2**

votes

**1**answer

90 views

### Numerical solution of singular ODE

Consider the singular ODE
$y''+\frac{y'}{r}+p(r)y=0 \ \ with \ \ y(0)=1 \ \ and \ \ y'(0)=0$.
Theoretically such solution exists and is unique if $p$ is nice. Is there a method to numerically ...

**7**

votes

**3**answers

5k views

### Interesting relationships between Cholesky decomposition and diagonalization

Let $\Sigma$ be a hermitian positive definite matrix and $L$ be it's Cholesky decomposition so that $LL^\ast=\Sigma$. Furthermore, let's diagonalize $\Sigma$ as $\Sigma = P\Lambda P^\ast$. $\Lambda$ ...

**1**

vote

**1**answer

78 views

### Splines linearly independent

Let $N_1:=\chi_{[0,1]}$ be defined as this characteristic function and $N_n:=N_{n-1}*N_1$ then this leads to polynomials with support $[0,n]$. These splines are well-studied click for wikipedia My ...

**7**

votes

**2**answers

2k views

### Eigenvectors of a symmetric positive definite Toeplitz matrix

I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better.
Although I assumed this would be a well ...

**0**

votes

**0**answers

148 views

### Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself).
I apologize if this question seems dumb; I'm a new ...

**6**

votes

**2**answers

625 views

### Conditions for convergence of Euler's method

It is known that a sufficient and necessary condition for
$$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$
to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...

**3**

votes

**2**answers

184 views

### What are interesting heuristics of determining how far given matrix is from a singular one?

The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more?
I think that over the years numerical folks (who are faced with ...

**1**

vote

**0**answers

81 views

### How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...

**3**

votes

**0**answers

34 views

### Quasi-M matrices?

Does any body know a reference on lower triangular matrices with negative entries everywhere except for the diagonal and subdiagonal where entries are positive (when all entries are negative with ...

**0**

votes

**0**answers

65 views

### Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of $\widetilde{...

**0**

votes

**0**answers

94 views

### Way to parameterise sparse multi diagonal matrix

I have an NxN matrix S that looks like this: $$ S^{-1} = K^{-1} + \Lambda $$
where N is a multiple of 3, both K and S are positive definite matrices, and Lambda is
$$
\Lambda = \begin{bmatrix}
x &...

**2**

votes

**2**answers

353 views

### Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:
$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,
where
(1) $A \in R^{n \times n}$ is a given matrix whose element ...

**1**

vote

**1**answer

91 views

### QR decomposition of matrix [closed]

I have matrix $M = \begin{pmatrix} A & B \\ B^T & 0\end{pmatrix}$, where $A$ is $N\times N$, $B$ is $N\times 2$ and I have $Q$, $R$ such that $A = QR$. What is the fastest way to find $Q'$ and ...

**7**

votes

**0**answers

205 views

### Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...

**7**

votes

**1**answer

170 views

### Compute only selected components of an eigenvector

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...

**4**

votes

**1**answer

169 views

### standard practice for large dense truncated svd computations?

What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large sparse matrices.
I assume for k small that you use a ...

**1**

vote

**1**answer

64 views

### Looking for algorithms based on sorting [closed]

i am looking for algorithms which use sorting in low-dimensional space like $R$ and how they are generalized for higher-dimensional spaces like $R^2$ where there is no sorting possible. (i.e. numbers ...

**2**

votes

**2**answers

245 views

### Matrix, singular values, Moore-Penrose-pseudoinverse

If A is any real mxn-matrix consider the block matrix
$\begin{pmatrix} E&A^T \\ A&0\end{pmatrix}$. This matrix seems to have close connections with pseudo inverse, svd etc. which are probably ...

**5**

votes

**3**answers

285 views

### Norm of triangular truncation operator on rank deficient matrices

Let $T_{n\times n}$ be a triangular truncation matrix, i.e.
$$T_{i,j}=\begin{cases}1 & i\ge j\\ 0 & i<j \end{cases}$$
It is known that for arbitrary $A_{n\times n}$
$$\|T\circ A\|\le\frac{\...

**0**

votes

**1**answer

272 views

### Proving that the eigenvalues of a certain matrix product are positive

Let $A$ be an $m \times n$ matrix, and define:
\begin{align*}
U &= {\rm diag} \{ \frac{1}{\beta_j} \}, \beta_j = \sum_{k=1}^m |a_{kj}|, j = 1 \dots n \\
V &= {\rm diag} \{ \frac{1}{\alpha_i} \}...