Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

1
vote
0answers
13 views

Conditional expectation of a set of Gaussian variables

I was wondering if there is an efficient way to compute the conditional expectation of every element in a Gaussian random vector ? Specifically: For a pair of Gaussian random variables $[x,y]$, the ...
0
votes
1answer
23 views

Gauß-Newton Example with one variable

$$T=f(t):=2 \alpha + \sqrt{\alpha^2+t^2}$$ To estimate $\alpha$ we got the measured values $T_i$ for $t_i$. Formulate the curve fitting problem and show each step in the Gauss-Newton algorithm. My ...
2
votes
2answers
45 views

Is this a circulant matrix?

It's symmetric, but I'm not sure whether it is circulant. In a question that I had asked on MSE a couple of weeks ago, several commenters had said that this is a circulant matrix, and to study the ...
2
votes
1answer
28 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
0
votes
1answer
27 views

Automatic way to have a good initial guess for the iterative methods ( newton method) and for high dimensional nonlinear problems

I am solving a variety class of nonlinear systems where I need to reduce in optimal manner the number of iterations of either the newton or modified newton method. For this end I am trying to figure ...
0
votes
0answers
29 views

How to calculate $det(X^T X)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
1
vote
1answer
46 views

How to numerically solve the Poisson equation given Neumann boundary conditions?

I want to solve the Poisson equation on a 2D domain given Neumann-type boundary conditions: The PDE: \begin{equation} \nabla^2 \; u(r,\theta) \;=\; f(r,\theta) \end{equation} The boundary ...
6
votes
0answers
63 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
0
votes
1answer
23 views

Stability of Gaussian elimination with and without pivoting [closed]

How do I explain why Gauss elimination without pivoting is not backward stable but it is with pivoting? (self-answered question)
0
votes
1answer
21 views

Can adding one column to a matrix increase its rank by more than one

Knowing the answer to this question would help me answer the following question: $A$ is an $m\times n$ matrix with $m>n$, and let $A=\hat{Q}\hat{R}$ be a reduced QR factorization. Suppose ...
0
votes
2answers
28 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
0
votes
0answers
22 views

Efficient method to compute grand sum of a Vandermonde matrix?

Is there a computationally efficient method to calculate the sum of all elements (grand sum) of a Vandermonde matrix? Each row can be quickly calculated using the formula for a geometric progression. ...
2
votes
0answers
50 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
0
votes
0answers
14 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
2
votes
2answers
36 views

Differential equation for finding closest point on surface.

Inspired by this question I got to think about a more general case. Say I have any discretized surface and want to find closest point from each point outside of surface to the surface. Say that I can ...
1
vote
0answers
25 views

How to apply Runge-Kutta to an implicit scheme?

I see there are some differences in the solution as I increase the resolution of my grid. I'm using Operator Splitting to solve Diffusion Reaction equation \begin{equation} \frac{\partial ...
1
vote
3answers
49 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
1
vote
0answers
9 views

Relationship between QR and LU factorization

Both algorithm return very similar results in terms of having a upper/right triangular matrix as one of the factors. What is the relationship between Q and L, and between R and U? What is the ...
0
votes
1answer
48 views

The MU-puzzle from GEB

The MUI system only uses the three letters M,U,and I to make strings. The system has four rules that allow you to make new strings out of existing strings by manipulating them. Rules 1 and 2 lengthen ...
1
vote
2answers
34 views

How to solve the system of equations $\{10^{-4}x_1+x_2=1, x_1+x_2=2\}$ using finite precision arithmetic with three significant figures?

Consider the following two equations: $10^{-4}x_1+x_2=1$ $x_1+x_2=2$ Solve using Gaussian Elimination using finite precision arithmetic with three significant figures. I'm a little ...
1
vote
1answer
28 views

Error bound of midpoint rules with unbounded second derivative

It is well known that error bound of midpoint rule for function $f[a,b]$ is given by $$ E\leq K\frac{(b-a)^3}{24 n^2} $$ where $|f(x)''\leq K|$ and $n$ is the number of time steps. if second ...
0
votes
0answers
16 views

Approximation of Mahalanobis distance

If $A$ is a symmetric positive definite $n\times n$ matrix then the square Mahalanobis norm of a vector $v\in \mathbb{R}^n$ is given by $$\lVert v \rVert_A^2=v^t A^{-1} v.$$ Now I have a situation ...
0
votes
0answers
13 views

Proof that Householder Triangularization for QR is backward stable

How do you prove that QR factorization via Householder Triangularization is backward stable? Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by ...
1
vote
0answers
23 views

How can I solve this specific set of equations?

Here are the equations: $$\sum_{k = 1}^n i_k + Y_n u_n = J \quad \quad (1)$$ $$i_1 + Y(u_1 - u_2) = J \quad \quad (2)$$ $$i_k - Y(u_{k - 1} -2u_{k} + u_{k + 1}) = 0, \quad \quad k = 2, ..., n - 2 ...
0
votes
0answers
22 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
1
vote
0answers
31 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
2
votes
0answers
16 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...
1
vote
1answer
30 views

What happens if the power method is applied with a starting vector $q=c_2 v_2+…+c_n v_n$ in the presence of roundoff errors?

Supose $\{v_1,...,v_n\}$ is an eigenvector basis and $|\lambda_1|>|\lambda_2|>\ldots >|\lambda_n|>0$, so, my question is, if our starting vector $q \in span\{v_2,\ldots,v_n\}$ and in the ...
1
vote
1answer
37 views

What are some Applications of Hermitian Positive Definite matrices?

I am learning about Hermitian positive definite matrices and the way that they can be decomposed with Cholesky decomposition. I have learned that these matrices deserve special attention for how often ...
0
votes
1answer
39 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
0
votes
1answer
29 views

How to link the eigenvalues to the components from PCA

I have a difference matrix from daily changes which I use to construct a covariance matrix. On this covariance matrix I use the power method to get the eigenvalues. The power method yields exactly the ...
0
votes
0answers
18 views

Is my QZ-Step as postulated in the paper?

I am working with the paper An algorithm for generalized matrix eigenvalue problems from C.B. Moler and G. W. Stewart (paper available here: ...
1
vote
0answers
26 views

Numerically finding eigenvalues of a Volterra operator of first kind

I'm looking for a solution to the following problem - $\int_{-\infty}^{\infty} K(x-y) f(y) = \lambda f(x)$ Consider $K(x-y) = \left\{ \begin{array}{lr} e^{-(x-y)} & : x > y \\ 0 & : x ...
1
vote
0answers
24 views

Ideas for expressing the inverse of matrix quadratic form $CAC^T$

I want to find an expression for the inverse of the matrix system $Z=CAC^T$, where $A \in \mathbb{C}^{n \times n}$ is block diagonal with dense blocks, and $C \in \{-1,0,1\}$ with dimension $m \times ...
2
votes
1answer
35 views

Solving a system of polynomials in $N$ variables

Suppose I am given some non-negative constants $(C_p)_{p=1, ..., l}$ and I would like to find an integer $N$ and vector $v \in R^N$ such that $$ \sum_{i=1}^N (v_i)^p = C_p $$ for $p=1, ..., l$. Can ...
1
vote
0answers
34 views

Eigenvalues after Givens-Rotation

Im just validating my own Code of a Givens-Rotation in Matlab. Therefore i let matlab compute the Eigenvalues after each Givens-Rotation. I am wondering why the Eigenvalues computed by matlab are ...
1
vote
2answers
60 views
+50

Solving a matrix equation using numerical optimization

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* ...
1
vote
0answers
37 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
0
votes
1answer
30 views

Use the Forward Difference method to approximate the solution to the following PDE?

Use the Forward Difference method to approximate the solution to the following PDE: $$ u^3\frac{\partial u}{\partial t}-x^2u\frac{\partial^2u}{\partial x^2}=2x^8t^7+6x^6t^5+4x^4t^3 $$ for $0\le ...
0
votes
0answers
14 views

QZ-Algorithm: how to simultaneously generate the upper triangular form

I need to calculate the Eigenvalues of a generalized Eigenvalue Problem. To achieve this, i wanted to use the QZ-Algorithm, which avoids calculating the inverse of a Matrix. This quite useful, because ...
2
votes
4answers
64 views

Inverse Chebyshev Recurrence

The Chebyshev polynomials (of the first kind) are a sequence of polynomials defined recursively by $$ \begin{cases} T_{0}(x) = 1 \\ T_{1}(x) = x \\ T_{n}(x) = 2xT_{n-1}(x) - T_{n-2}(x) \end{cases} $$ ...
1
vote
0answers
52 views

complex rank-one update

I'm trying to find the eigendecomposition of a rank-one update to a complex matrix $D + uv^T$. The matrix $D$ is diagonal, but not the identity. It has unique imaginary entries along the diagonal. ...
1
vote
0answers
38 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, ...
0
votes
0answers
35 views

Givens-Rotation from the right

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this topic givens rotation from right side but i could not really understand the ...
5
votes
1answer
18 views

Proving a property about Gauss-Seidel

This is a homework problem, so please give hints or tips instead of full answers. The problem is as follows: Let $G$ be the iteration matrix of the Gauss-Seidel method; i.e. $$G=I-(D-L)^{-1} ...
0
votes
0answers
8 views

Conversion of cylindrical harmonic field into space-harmonic field for plane waves

It is well known that a plane wave can be represented by an infinite sum of cylindrical wave function of the form $\varphi^i(\rho,\phi)=e^{\left(-j\beta \rho ...
0
votes
0answers
15 views

PCA when SVD is a skinny SVD

A = m * n matrix. When $m \ge n$, it is easy to see that the V matrix in the full SVD ($A = U*S*V^T$, where U and V are both orthonormal square matrix) and V in a skinny SVD are the same. When $m \lt ...
1
vote
0answers
22 views

Overdetermined system with discrete data.

The setup I have a set of experimental data (subscript 1) which calculates two variables $u_1(x,y,z)$ $v_1(x,y,z)$ I can calculate the three spatial gradients for my two variables ($u_1$ and ...
1
vote
0answers
26 views

QR Algorithm fails under certain conditions

First of all, i have to admit that i am really knew to this numeric stuff. I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am ...
0
votes
2answers
21 views

Special properties in the direct solving of sparse symmetric linear systems

In the area of computational solving of large sparse linear systems, some solvers specialize only on symmetric sparse matrices, be it positive definite or indefinite as compared to general ...