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

learn more… | top users | synonyms

1
vote
0answers
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
0answers
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
0answers
49 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
1answer
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 ...
0
votes
0answers
82 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
1answer
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
0answers
31 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
0answers
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....
7
votes
2answers
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$ ...
2
votes
0answers
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
0answers
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
1answer
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
1answer
34 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
1answer
85 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
2answers
289 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
0answers
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
1answer
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 ...
8
votes
1answer
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-...
6
votes
2answers
266 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
0answers
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
1answer
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
2answers
73 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
1answer
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 ...
0
votes
0answers
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 ...
3
votes
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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 &...
1
vote
1answer
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
2answers
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
2answers
629 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
2answers
846 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
1answer
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
1answer
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
1answer
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} \}...
2
votes
2answers
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 ...
4
votes
1answer
94 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
3answers
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{\...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
4
votes
4answers
678 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
1answer
80 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
1answer
213 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
0answers
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
2answers
193 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
1answer
248 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
1answer
114 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\|...