All Questions
Tagged with linear-algebra na.numerical-analysis
176 questions
1
vote
0
answers
125
views
smallest singular value over invertible sub-matrices
Consider the matrix $M = \begin{bmatrix} A & A B \end{bmatrix} \in R^{n \times (n+m)}$, with $A \in R^{n\times n}$, $B \in R^{n \times m}$, $m < n$, $m > 1$, $A$ symmetric positive definite.
...
- 303
10
votes
2
answers
2k
views
Is there a standard name for (non-square) matrices with orthonormal columns?
One encounters often in numerics non-square matrices with orthonormal columns, i.e., $U\in\mathbb{R}^{m\times n}$, with $m > n$, such that $U^TU=I$ (but, clearly, $UU^T \neq I$).
Is there a name ...
- 20.2k
2
votes
0
answers
2k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
- 121
4
votes
3
answers
283
views
Iterative matrix inversion with $L^\infty$ norm
The usual conjugate gradient type algorithms for iteratively finding the inverse of a matrix applied to a vector, $x = A^{-1} y$, works by minimizing $\|Ax - y\|^2$ where $\| \cdot \|$ is the $L^2$-...
- 1,150
4
votes
2
answers
948
views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
- 41
4
votes
2
answers
383
views
Question about preconditioning
I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here.
I understand that for many iterative methods, convergence rates can be shown ...
- 43
1
vote
0
answers
556
views
Sign correction for SVD in Matlab [closed]
I have a Matlab function that runs a SVD. Unfortunately, the function [U,S,V] = svd(A) has a sign ambiguity which could give misleading results in my application. ...
- 11
1
vote
0
answers
286
views
Generalized eigenvalue problem with nonnegative eigenvector constraint
Consider the following problem that is known to be non-convex but can be solved as a generalized eigenvalue problem (i.e. has a global optimum solution):
$\underset{w}{\text{maximize}}\quad w^{\top}...
- 11
8
votes
2
answers
950
views
Best known bounds on (border) ranks of small matrix multiplication tensors?
The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. ...
- 7,633
1
vote
0
answers
174
views
Negative eigenvalue of Toeplitz Hermitian matrix?
I am working on estimation of a covariance matrix and I know that the matrix is Toeplitz. The desired matrix should not produce negative eigenvalues at all. However, sometime my estimation leads to a ...
- 495
10
votes
1
answer
449
views
How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently
Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute
$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$
One option is to simply ...
- 3,377
1
vote
0
answers
90
views
Separable Least squares - is there a notion of conjugate directions?
I have a general question.
Suppose I have the following to optimize
$$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$
where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
- 61
1
vote
0
answers
227
views
Find optimal value for a regularization parameter in generalized eigenvalue problem
Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
- 45
1
vote
1
answer
940
views
Uniqueness and invariance of the LDLT decomposition
A real symmetric positive semi-definite matrix $A$ can be decomposed in the form
$A = P^TLDL^TP$,
where $P$ is a permutation matrix, $L$ is a lower unit triangular matrix and $D$ is a diagonal ...
- 101
12
votes
2
answers
5k
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 ...
- 253
0
votes
1
answer
338
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 ...
- 253
2
votes
0
answers
193
views
How to find moment condition for generalized method of moments?
Consider a scalar system with $2K$ outputs and $K+2$ unknowns:
$y_{k,1}=x_ka_1+n_{k,1} \quad y_{k,2}=x_ka_2+n_{k,1}$.
The variables $n_{k,\ell}$ are zero mean noise variables.
To estimate $a_1$ and $...
- 21
0
votes
2
answers
1k
views
The condition number of a scaled Vandermonde matrix
Let $V(x_1,..,x_n)$ be the Vandermonde matrix induced by $x_1,..,x_n$, and
let $\tilde{V} := V(\frac{x_1}{h},...,\frac{x_n}{h})$.
My intuition says that the condition number should be invariant under ...
- 265
4
votes
0
answers
233
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.,...
- 1,517
7
votes
1
answer
449
views
Can I find the gap between the two least eigenvalues of this special matrix A(t)?
I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal non-...
- 103
0
votes
2
answers
321
views
Solving sparse linear least squares or a positive definite 5-band matrix system fast
I want to quickly solve the following linear least-squares problem
$$\min_{x \in \mathbb{R}^n} \left\| A x - b \right\|_2^2$$
with a special sparse structure where each row in $A$ has only up to $4$ ...
- 101
1
vote
1
answer
279
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 ...
- 231
1
vote
0
answers
98
views
LU growth factor applied to LDL of a Positive Semidefinite matrix [closed]
For a Positive Semidefinite matrix $A$, which we can decompose through $LDL$ decomposition as follows: $A=LDL^\text{T}$; how can we prove that for a decomposition $A=LU=L(DL^\text{T})$, the growth ...
- 111
0
votes
0
answers
83
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{...
- 13.9k
0
votes
1
answer
98
views
What is exponentially fitted osculating straight line?
While reading an article about iterative methods for solving nonlinear equations I can't understand what is exponentially fitted osculating straight line. Could someone please briefly explain this ...
- 163
4
votes
1
answer
396
views
Resolvent of a triangular matrix
Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?
Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the ...
- 333
7
votes
1
answer
197
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}$, ...
- 91
0
votes
1
answer
769
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} \}...
- 3
4
votes
1
answer
161
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 ...
- 20.2k
2
votes
2
answers
219
views
Boundedness of ratio of linear functions
Consider the function
\begin{eqnarray}
f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i},
\end{eqnarray}
over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
- 23
2
votes
2
answers
607
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 ...
- 241
4
votes
1
answer
538
views
Rank 1 Approximation of Elementwise Inverse Matrix
I'm wondering whether there is a good way to solve the following optimisation problem.
Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that
$$ \| D_1 A ...
- 909
1
vote
0
answers
1k
views
Bounds for the infinity norm of the inverse for certain diagonaly dominant matrices
I m trying to analyse the stability against perturbations for a specific system of linear equations $Ax=b$.
For this, i use the standard condition number $||A||_{\infty}||A^{-1}||_{\infty}$.
Here ...
- 11
1
vote
1
answer
474
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 ...
- 2,205
2
votes
1
answer
78
views
An algebraic equation question [closed]
My question is this:
If $\frac{\sqrt[n]{\prod_{i=1}^n(p_i + 1)}}{\sqrt[n]{\prod_{i=1}^n(m_i + 1)}} = e ^\beta$
can I find an expression (either exact or approximate) for $\frac{\sqrt[n]{\prod_{i=1}^...
- 163
2
votes
0
answers
146
views
Lanczos algorithm with thick restart on a dynamic matrix
currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
- 21
4
votes
0
answers
136
views
What do we know about the generalized eigenvalue problem involving a projector?
Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$.
Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem
$$...
- 325
2
votes
0
answers
263
views
Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix
I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...
- 21
1
vote
1
answer
83
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 ...
- 45
1
vote
1
answer
246
views
Eigenvalue problem with quadratic constraints
$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$
where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = (x_{1},x_{2},.....
- 45
2
votes
1
answer
1k
views
Updating $LU$ decomposition after adding a sparse matrix
How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...
- 2,205
12
votes
2
answers
3k
views
How to project a vector onto a very large, non-orthogonal subspace
I have a difficult problem.
I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...
- 223
5
votes
0
answers
392
views
Preconditioner for finding the smallest eigenpairs 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 $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
- 500
2
votes
1
answer
276
views
Possible pathological properties of positive definite matrix
Suppose $A$ is a positive definite matrix such that$$ I \preceq A \preceq 1.01I.$$ Is it possible that $\sum\limits_{i=1}^n A_{1i}$ can be arbitrarily large?
- 55
8
votes
0
answers
481
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 ...
- 489
13
votes
2
answers
946
views
Computing a large permanent
Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
- 6,962
7
votes
1
answer
318
views
Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?
Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
- 325
6
votes
1
answer
1k
views
Efficient computation of Markov chain transition probability matrix
Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
- 63
0
votes
1
answer
173
views
Avoiding epsilon in mixed integer linear and quadratically constrained programs
I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 \...
- 1
4
votes
1
answer
885
views
best rank r approximation for non-Frobenius norm
The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...
- 263