Questions on the various algorithms used in linear algebra computations (matrix computations).
5
votes
0answers
84 views
numerical linear algebra tricks for repeated sums and inversions with symmetric positive-definite matrices
I'm doing the following procedure to get the max-likelihood estimate of a matrix-variate normal distribution from $r$ samples of matrices in $\mathbb{R}^{n \times p}$ (algorithm from Dutilleul ...
4
votes
0answers
151 views
Computing the SVD factorization on C++ (using the proof of the existence of the SVD factorization)
I am doing a C++ program that computes the SVD factorization of a real matrix A without using any known library of algebra that contains the implementation. In addition, QR descomposition is not ...
4
votes
0answers
222 views
Simulating from a Multivariate Gaussian without Cholesky
I'd like to draw a sample from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$, where $\mu$ is the mean vector (can assume it to be $\boldsymbol{0}$), and $\Sigma$ is a sparse positive ...
4
votes
0answers
60 views
Is there a way to exploit the fact that the covariance matrix has a blocked structure to more easily compute the multivariate normal density?
I'm trying to minimize the (negative) multivariate normal log likelihood (dropping constants):
$$
\log |\boldsymbol\Sigma|\,+(\mathbf{x}-\boldsymbol\mu)^{\rm ...
3
votes
0answers
155 views
Trace Minimization of Covariance Matrix
Given a matrix X whose rows contain observations collected at some locations.
Can someone explain how trace minimization of covariance matrix $XX^T$ can lead to orthogonal / mutually independent ...
3
votes
0answers
195 views
Why is Cholesky factorization numerically stable
It's often stated (eg: in Numerical Recipes in C) that Cholesky factorization is numerically stable even without column pivoting, unlike LU decomposition, which usually need pivoting schemes.
But ...
3
votes
0answers
69 views
What's the state of the art for computing the largest singular value of a matrix
My matrix is not sparse, and is sized 30k by 30k. Most importantly, the gap between the largest and the second largest singular values is small or even 0.
ARPACK, SLEPc, Matlab, PROPACK? Which ...
3
votes
0answers
405 views
Numerical methods to find eigenvectors with 0 eigenvalue
I'm curious if there's any numerical way of directly finding the eigenvectors with eigenvalue 0.
If I didn't have to do it directly, I would probably do it like this in pseudocode:
...
2
votes
0answers
25 views
Solver for sparse linearly-constrained non-linear least-squares
Reposted from stackoverflow on the advice of Nick Rosencrantz:
Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and ...
2
votes
0answers
35 views
Determinant error bound is better than norm bound for matrix product
In by textbook on numerical algebra, it states that for a numerical matrix product the error bound:
$|A B - \hat{A} \hat{B}| \le c|A| |B|$
is a stronger expression than
$\|A B - \hat{A} ...
2
votes
0answers
33 views
maximal m-elements of the matrix inversion
Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
2
votes
0answers
26 views
Customising force-directed graph layout
I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
2
votes
0answers
51 views
Orthonormal Matrix weighted regression
$Q$ is a rectangular matrix with orthonormal columns. A linear system composed of $$Qx= b$$ is really easy to solve as:
$$Q'Q=I$$
hence:
$$x=Q'b$$
Given that $Q$ is orthonormal can this be used to ...
2
votes
0answers
60 views
$l^1$ norm estimate for inverse of Vandermonde matrix
As title, I would like to know the known upper bound for the $l^1$ norm for inverse of Vandermonde matrix. A quick search gives this paper by Gautschi 40 years ago, but it deals with the infinity norm ...
2
votes
0answers
63 views
Showing that the least-square method minimizes error
Assume that the relation between temperature and time is defined as follows:
$$T = A^kC$$
We can find parameters $A$ and $C$ using the least-square method. The given relation is not linear, but we can ...
2
votes
0answers
32 views
commuting a LU factorisation
Consider the permutation matrix
$P= \begin{pmatrix}
0 & \cdots & 0 & 1 \\
0 & \cdots & 1 &0 \\
\vdots & \ddots & \vdots & \vdots \\
1 & \cdots ...
2
votes
0answers
72 views
Check for Ill Conditioned matrix
How can I efficiently check if a tridiagonal system with 1's in diagonal is ill-conditioned or not ? The common way is to get the ratio of largest and smallest singular values and see if its greater ...
2
votes
0answers
52 views
QR decomposition help
What do Q and R stand for?
Why must the diagonal entries of R be positive instead of just nonzero?
2
votes
0answers
23 views
Re-calculate solution after altering some elements in a linear system
Problem
I have a linear system:
$$ Mx = b $$
$M$ is like a Band Matrix. And assume I have a solution $x_{init}$ at beginning.
There will be some operations which are going to alter some elements in ...
2
votes
0answers
64 views
Spectral/ Eigen-Value solution with a linear constraint?
Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
2
votes
0answers
125 views
The norm of the matrix
This problem is in Trefethen'book Numerical Linear Algebra
Suppose the $m\times n$ matrix $A$ has the form
$A=\begin{pmatrix}A_1\\A_2 \end{pmatrix}$
where $A_1$ is a nonsingular matrix of dimension ...
2
votes
0answers
72 views
Need little hint to prove a theorem .
I have an iterative method \begin{eqnarray}
X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots
\end{eqnarray}
with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
2
votes
0answers
323 views
General properties of eigenvalues of a Jacobian matrix when premultiplied by a symmetric, positive definite matrix?
For a particular engineering problem that I'm working on, I have computed a Jacobian matrix $J$ and there is another matrix $M$ associated with the problem. $M$ is known to be symmetric, real-valued, ...
2
votes
0answers
82 views
(Experimental) Can it be shown that this extension of the secant-interpolation has quadratic convergence?
Background: I needed some efficient but simple interpolation-methods aside of Newton's iteration because I want to have it in contexts, where the derivative of a function is not always known. So an ...
2
votes
0answers
82 views
Question on “avoidance of crossing”
In review of linear algebra I come across this phenomenon, the Google Book link is this:
What I do not understand is Lax tried to persuade us that "there is another way of parametrizing these ...
2
votes
0answers
347 views
QR with column pivoting
Golub and van Loan's algorithm 5.4.1
for QR factorization is suitable as a rank revealing algorithm.
The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
1
vote
0answers
29 views
What is the Moore-Penrose pseudoinverse for scaled linear regression?
The matrix equation for linear regression is:
$$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$
The Least Square Error solution of this forms the normal equations:
$$ ({\bf{X}}^T \bf{X}) \vec{\beta}= ...
1
vote
0answers
16 views
Short-cut to a group of long sums/differences
If I have data $a,b,c,d$, and want to calculate $x=a+b-c-d$, $y=a-b-c+d$ and $z=a+b+c-d$,
I can save three adds by doing $e=a-c$, $f=b-d$, then $x=e+f$,$y=e-f$, $z=a+c+f$.
If I have 100 data values ...
1
vote
0answers
20 views
Numerical Methods for eigen values of $A \in \mathbb{C}^{n \times n} $
I've been writing a linear algebra library in c# for a while as an intellectual exercise and its gotten vastly more sophisticated that I originally thought it would and when I started adding methods ...
1
vote
0answers
40 views
Existence criteria for the LU decomposition of a tridiagonal matrix
In this link, the following result is presented without proof:
Let $a, b, c$ be the lower off diagonal, diagonal, and upper off diagonal elements of a tridiagonal matrix. A pivotless LU ...
1
vote
0answers
41 views
About the Generalized singular value decomposition (GSVD).
I have studied about Singular value decomposition (SVD) and had solved few numerical examples to understand SVD. Now I am studying Generalized singular value decomposition (GSVD). I followed this ...
1
vote
0answers
24 views
Algorithm to compute similarity computation
I have a similarity transformation of matrices from the type $B = P^{-1}AP$. It is known that $A$ and $P$ are invertible matrices, but not orthogonal.
Given that I have the matrices $P$ and $A$ I ...
1
vote
0answers
27 views
Multigrid Interpolation and Restriction operators
I have a question about the restriction and the interpolation operators of a Multigrid algorithm.
Let those be given:
The full weighting restriction stencil (in 2D): $\frac{1}{16} \left[ ...
1
vote
0answers
24 views
Preconditioning and effects on precision of solution of LSE
In my courses on numerical analysis I have been tought that the main and principle motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers ...
1
vote
0answers
44 views
Eigenvalues of discretized linear integral operator
Suppose I have the following kernel operator:
$Af(x) = \int_{-1}^1 K(x-y)f(y)dy$
which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
1
vote
0answers
46 views
Criterion for detecting rank-deficiency via QR decomposition?
I apologize in advance if this is an ill-posed question -- I'd appreciate advice on what pieces are missing as much as an answer.
I'm solving a system like $P \approx X Y^T$, where P is a large ...
1
vote
0answers
43 views
Nearest point to a convex polytope
I am looking for fast, memory-efficient computational algorithms to solve the following problem:
Minimize: $||x - x*||_2^2$, subject to constraints $A x = a, B x <= b, l <= x <= u$,
where ...
1
vote
0answers
63 views
Weighted linear least squares parameter covariance
I am currently trying to figure out the parameter covariance for a weighted linear least squares problem where
$$y = X\beta$$
The parameters for which my objective function is lowest are given by
...
1
vote
0answers
18 views
How to construct an optimal subspace with 3 indices.
I have a 3-dimensional array that is potentially very large and I need to do quite a lot of operations with it.
Is there a systematic way to choose a subspace of a certain size, such that the norm ...
1
vote
0answers
81 views
covariance matrix eigenvalues eigenvectors
Is there a probabilistic or analytical meaning of the eigenvalues/eigenvectors
of covariance matrix of multivariate normal distribution?
Thank you
1
vote
0answers
36 views
Numerical linear algebra spectral norm limit.
Let $A \in \mathbb{R}^{m \times n}$ be of full rank. Consider
$X_{k+1}=(2k-X_{k}A)X_{k}$, $X_0 = \alpha A^{T}$.
Let $E_k = I-X_kA$,
Deduce that if $||E_{0} ||_{2}<1$, then $lim_{k \rightarrow ...
1
vote
0answers
41 views
Solution to pertubed linear system
Suppose one has the following system of linear equations
$$(A + \Delta A) x = b$$
where $A$ and $\Delta A$ are large sparse matrices and $\Delta A$ is "small" compared to $A$, furthermore vector $x$ ...
1
vote
0answers
51 views
fixed point spectral radius
We have the following stationary matrix iteration
$$x_{k+1} = Mx_k + c$$
where $M$ is nxn matrix and $c$ is a vector.
Let $r(M)$ denote the spectral radius of $M$.
Show that spectral
radius ...
1
vote
0answers
128 views
Numerical Linear Algebra problem (QR factorization with column pivoting)
For matrices that might be rank deficient it is common to incorporate pivoting in Householder QR factorization of A $\in$ $\Re^{mxn}$ (m $\geq$ n). Let $A^{(k)}$ denote the matrix at the start of the ...
1
vote
0answers
64 views
Show that its a Generalized Eigenvalue problem
Show that the minimizer is obtained by a generalized eigenvalue problem.
$$\alpha=\underset{1^TK\alpha=0; \ \alpha^TK^2\alpha=1}{\text {arg min}} \gamma ||f||_{K}^2+f^TLf$$
Details:
$K$ ...
1
vote
0answers
94 views
Simultaneous Eigenvalue Problem
I have what I think is a simultaneous eigenvalue problem in three parameters:
$$\alpha A_1x + \beta B_1x + \gamma C_1x + D_1x = 0$$
$$\alpha A_2x + \beta B_2x + \gamma C_2x + D_2x = 0$$
$$\alpha A_3x ...
1
vote
0answers
34 views
Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability
I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
1
vote
0answers
105 views
Finding a row permutation that makes a matrix more “blocks-like”
Disclaimer: what follows arise in a context from Computer Science, but it seems to me that my questions were more likely to be solved from mathematicians than from computer scientists.
Let suppose ...
1
vote
0answers
798 views
What is the algorithm for LU factorization in MATLAB?
What is the algorithm for LU factorization in MATLAB, i.e. [L,U] = lu(a)?
After searching for many examples and trying to compare the result with MATLAB,
they are ...
1
vote
0answers
69 views
How to solve Rayleigh Quotient type problem?
How to solve Rayleigh Quotient type problem?
$$\max (w+w_0)^tC(w+w_0)
\text{ s.t. } w'w=1,$$
where $w_0$ is given.
Thank you!
