# Tagged Questions

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

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 ...
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. ...
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 ...
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 ...
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/...
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 ...
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 ...
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 ...
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 ...
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....
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$ ...
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 ...
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}$. ...
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 ...
34 views

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.,...
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 ...
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 ...
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 ...
148 views

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 ...
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 ...
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) ...
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 ...
65 views

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{... 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 &... 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 ... 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 ... 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_0to have a unique solution is f Lipschitz in y and continuous in t. However, ... 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\\ && \... 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 ... 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}, ... 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} \}... 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 ... 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 ... 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{\... 2answers 438 views ### Are there some algorithms to solve the diagonal matrixX$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 ... 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 ... 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 |$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 ... 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 ... 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: A = \left[\begin{array}{c|c} \... 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,$...
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 ...
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\|...