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

**3**

votes

**1**answer

116 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 ...

**0**

votes

**0**answers

80 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/...

**1**

vote

**1**answer

50 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 ...

**4**

votes

**1**answer

96 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 ...

**3**

votes

**0**answers

84 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 ...

**0**

votes

**0**answers

23 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 ...

**1**

vote

**0**answers

38 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....

**7**

votes

**2**answers

238 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$ ...

**2**

votes

**0**answers

65 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

79 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

78 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 ...

**10**

votes

**2**answers

283 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

68 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

53 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 ...

**8**

votes

**1**answer

260 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-...

**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 + ...

**3**

votes

**0**answers

107 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 ...

**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

**1**answer

76 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 ...

**0**

votes

**0**answers

147 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 ...

**3**

votes

**2**answers

183 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

93 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 &...

**1**

vote

**1**answer

90 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

**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 ...

**6**

votes

**2**answers

570 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, ...

**5**

votes

**2**answers

796 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\\
&& \...

**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 ...

**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}$, ...

**0**

votes

**1**answer

270 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} \}...

**2**

votes

**2**answers

241 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 ...

**4**

votes

**1**answer

93 views

### Sensitivity of the range of a matrix

The distance between two subspaces $\mathcal{U}$ and $\widetilde{\mathcal{U}}$ is classically defined as $d(\mathcal{U},\tilde{\mathcal{U}}):=\|P-\tilde{P}\|$, where $P$ and $\tilde{P}$ are orthogonal ...

**5**

votes

**3**answers

283 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{\...

**1**

vote

**2**answers

426 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 ...

**2**

votes

**2**answers

352 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 ...

**4**

votes

**4**answers

666 views

### Determinant of sum of Kronecker products

Given four real symmetric matrices $A,B \in \mathbb{R}^{n \times n}$ and $C,D \in \mathbb{R}^{m \times m}$, is there an efficient way to compute the determinant:
$\det|A \otimes C + B \otimes D |$

**0**

votes

**1**answer

77 views

### Large scale least squares of non symmetric and non square problems

Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$).
There is a large amount of algorithms for symmetric ...

**1**

vote

**1**answer

209 views

### Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form
$$A_{n\times n}\cdot x=1_n$$
where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...

**4**

votes

**0**answers

117 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form:
\begin{equation}
A =
\left[\begin{array}{c|c}
\...

**4**

votes

**2**answers

188 views

### QR-Decomposition of matrix valued function

Suppose I have a matrix valued function
$$
F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T
$$
where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, $...

**3**

votes

**1**answer

246 views

### submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...

**-1**

votes

**1**answer

113 views

### Convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $\|u\|=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$.
I have that $\|u^{k+1}-u\|\leq \|I - c A\|\|u^k-u\|...

**0**

votes

**1**answer

204 views

### Perturbation of Cholesky decomposition for matrix inversion

I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$
where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...

**11**

votes

**2**answers

557 views

### Determinant and eigenvalues of a specific matrix

This came up in a conversation with an engineer friend of mine.
Let $c>0$ be a constant. Let $A_{ij}$ be an $n$ by $n$ matrix with entries
$$
A_{ij} = e^{-c(i-j)^2}.
$$
Is there a name for this ...

**1**

vote

**1**answer

72 views

### Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...