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

learn more… | top users | synonyms

0
votes
0answers
12 views

How many kind of basis function to approximate an arbitrary function

I am finding a list algorithm to approximate an arbitrary function. Such as Bernstein, he said that a linear combination of Bernstein basis polynomials $$B_n(x) = \sum_{\nu=0}^{n} \beta_{\nu} ...
0
votes
1answer
20 views

Problem implementing a QR factorization

I'm trying to write a Fortran subroutine to compute a QR factorization using the Householder method. To test my routine, I compute the factorization of the following matrix: $$ A = \begin{pmatrix} ...
2
votes
0answers
11 views

LU factorization accuracy

I'm doing some experiments with LU factorization (without pivoting). Basically I have a 2x2 matrix and a $b$ vector and I try to solve Ax=b. $A$ looks like: \begin{pmatrix}a&1\\1&1\\ ...
1
vote
0answers
11 views

Reduction of matrix $A$ to $B$ to find eigenvalues by Power method [duplicate]

How to reduce matrix $A$ to $B$ such that it has all eigenvalues and eigenvectors of $A$ but the dominant eigenvalue (eigenvalue with largest magnitude) is replace by $0$ ? I am using Power method to ...
0
votes
0answers
15 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
-2
votes
1answer
27 views

Linear Algebra - minimal polynomial, polynomial

the minimal polynomial of $A$ is $(xāˆ’1)(x+1)$. Let $f(x)=4x^{2008} āˆ’ 8x^{597} + 10x + 6$ show $f(A) = \alpha I + \beta A$ $\alpha=?\ \beta=?$ So I worked on a bit, and I got this far $A = ...
0
votes
0answers
18 views

How to implement QR method for bidiagonal matrices?

My goal is to take the singular value decomposition of a (not necessarily square) matrix. I have a method to do bidiagonalization of a matrix, and I can chop the bottom rows of zeros. In order to find ...
1
vote
0answers
11 views

SVD of a block partitioned matrix

Given a block partitioned matrix $\boldsymbol{A}$ $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{A}_{1,1} & \boldsymbol{A}_{1,2} & \cdots \\ \boldsymbol{A}_{2,1} & ...
0
votes
0answers
23 views

Fast method for getting solution for underdetermined equation system

What is a fast and stable method for getting a solution for an underdetermined equation system which could be applied by a computer?
0
votes
0answers
18 views

Help understanding Jacobi SVD

I found this link, and I want to complete this implementation of the Jacobi SVD method, but it isn't clear to me how to implement alpha, beta, and gamma. I think it's very clear that ...
2
votes
2answers
14 views

convergence of iterative methods for linear system

Here is a theorem about convergence of iterative methods for linear system in Burden and Faires' book "Numerical Analysis" For any $x_0 \in \mathbb{R}^n$, the sequence defined by $x^k = Tx_{k-1} + c$ ...
0
votes
0answers
4 views

Find rank-vital rows (coloops) of a matrix

Let $A$ be a $m\times n, m\geq n$ matrix over a finite field. Coloop is any row of $A$, such that the rank of $A$ is decreased when that row is removed. What is an efficient algorithm to find all the ...
0
votes
2answers
19 views

What is the intuition behind matrix splitting methods (Jacobi, Gauss-Seidel)?

Descent Methods, like Gradient and Conjugate Gradient ones, have a nice geometric interpretation and I really love them. What about Jacobi, Gauss-Seidel or other matrix splitting methods? I can't see ...
0
votes
1answer
21 views

Diagonal of multidimensional DFT

If $X$ is a $n\times n$ square matrix and $F$ its Discrete Fourier Transform, is there a way to compute the diagonal $(F_{1,1},\ldots,F_{n,n})$ without explicitly computing the full DFT? How about ...
2
votes
1answer
25 views

How to prove that the inner product is positive unless $Ax = b$?

Suppose $Ax =b$, then the equation above = $0$ Spp $Ax \neq b$, since $A$ is positive definite, then Am I going to the right direction for this proof? How can I show the rest is positive as ...
0
votes
1answer
28 views

Sum of orthogonal matrices

Consider the subspace $\mathbb{R}^m$ with usual inner product.Let $S_1$ and $S_2$ subspaces of $R^m$, $P_1\in M_m(\mathbb{R})$ the orthogonal projection matrix on $S_1$ and $P_2\in M_m(\mathbb{R})$ ...
3
votes
0answers
23 views

What does affine invariance mean in the context of the Newton's method?

The textbook Numerical Solution of Boundary Value Problems for Ordinary Differential Equations (by Ascher, Mattheij, and Russell) states on page 329: [W]e observe that Newton's method is affine ...
-4
votes
1answer
30 views

Orthogonality and inner product [closed]

Let $A\in M_2(\mathbb{R})$ a positive definite matrix and the application $F:\mathbb{R}^2 \times \mathbb{R}^2\rightarrow \mathbb{R}$ $$F(x,y)=y^tAx$$ If ...
1
vote
1answer
23 views

Show that a positive definite (not necessarily symmetric) matrix induces a hyperellipse

Consider $A\in M_n(\mathbb{R})$ a positive definite matrix and a matrix $B\in M_{n \times p}(\mathbb{R})$, with $n\geq p$ and $rank(B)=p$. i) Show that $C=B^TAB$ is positive definite. ii) Show that ...
1
vote
1answer
25 views

Problem with Broyden update: Divide by a matrix?

I am implementing a maximum likelihood method (the EM algorithm) for which I'm using Broyden's method at each iteration. Here is the formula: $\Delta A = \frac{(\Delta \theta - A ...
3
votes
1answer
58 views

Find desired root (based on certain constraints) while using Newton-Raphson method

My function is a vector of dimension 6, and on using Newton Raphson method, the solution usually converges to the nearest root. However, I know that my function has multiple roots (it's an Inverse ...
1
vote
0answers
36 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
27 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
7
votes
1answer
66 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
0
votes
0answers
26 views

QR method for Hessenberg matrices

In trying to implement the method, my approach is to use a reduction to Hessenberg form, and then to iterate using a QR method of Givens rotations. However, I am having trouble successfully ...
1
vote
1answer
37 views

Convergence of the LR algorithm for $2\times 2$ SPD matrices

I've been asked to prove that the following iterations converge to the eigenvalues of SPD $A_0 \in \mathbb{R}^{n \times n}$ $A_0 = \begin{bmatrix}a & b\\ b & c \end{bmatrix}$ with $a \geq ...
0
votes
1answer
15 views

efficient computation of Cholesky decomposition during tridiagonal matrix inverse

I have a symmetric, block tridiagonal matrix $A$. I am interested in computing the Cholesky decomposition of $A^{-1}$ (that is, I want to compute $R$, where $A^{-1}=RR^T$). I know how to compute the ...
0
votes
1answer
30 views

Relationship between eigenvectors of two matrices

Suppose I have matrix $A \in R^{2n \text{x} 2n} $ given by $X^{-1} diag(W - iY, W + iY) X$ and matrix $B \in C^{n \text{x} n}$ and $B = W + iY$. Let $v$ be an eigenvector of $A$. How can I relate ...
1
vote
1answer
34 views

Hessenberg reduction

Given $A \in \mathbb{R}^{nxn}$ and $z \in \mathbb{R}^n$, find orthogonal $Q$ such that $Q^TAQ$ is upper Hessenberg and $Q^Tz = \beta e_1$. My attempt so far, Individually I can find the Householder ...
2
votes
1answer
78 views

double root and newton method, a problem on solved exercise? [closed]

$f(x)$ in $x= \alpha$ has double roots and define in $\alpha$ neighbor. if the sequence $\{x_n\}$ for solving $f(x)=0$ calculated by newton methods the following is correct. ($a$ and $b$ is plasced ...
1
vote
1answer
61 views

questions on polynomial Lagrange Interpolation of order $n$?

I ran in One Ex in my book when Iā€Œ prepare for final exam on numerical method. how can help me how we solve such a problem? if $P(x)$ and $Q(x)$ be two polynomial Lagrange Interpolation of order $n$ ...
1
vote
2answers
30 views

solving given linear equation

So before you guys judge me, I honestly am so clueless with this so please bare with my dumb questions. I have been at this equation that I've been going for an hour now, $\frac{(3x-1)}{2} -2 = ...
3
votes
0answers
57 views

How do I apply this PDE as an image filter?

I'm trying to preprocess a height map image with a helmholtz-type equation as described in this paper. The equation is: $$ddx(h') + ddy(h') + y(h'-h) = 0$$ I solved for h and got: ...
0
votes
2answers
43 views

How to minimize $w^{T}Aw$?

$A$ is $n\times n$ matrix. Find a $w$ ( $n$-dimensional unit vector) which minimizes this function. By $w^{T}$, I mean $w$-transpose. I understand there would be non-linear optimization techniques ...
0
votes
2answers
25 views

Decomposition of a diagonal matrix into a product of particular matrices.

Could you tell me please, if it's possible to find a decomposition of a diagonal matrix $ 3 \times 3 $ : $ D ( \lambda_1 , \lambda_2 , \lambda_3 ) = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 ...
0
votes
0answers
19 views

Generate duplicate element from a matrix by formula $b(i:j)=A(i:j,:) \times A^{-1} \times b$

I have an interesting question about generate duplicate elements from matrix. I assume that I have a matrix A (such as the bellow example $5 \times 5$) and vector $b$ is $5 \times 1$. My goal is make ...
1
vote
1answer
65 views

Properties shared by similar and unitary similar matrices.

We know that matrices $A$ and $B$ are similar if there exists an invertible matrix $P$ such that $A=PBP^{-1}$ and they are unitarily similar if $P$ is unitary ($PP^*=P^*P=I$). I want to know : What ...
2
votes
1answer
46 views

SVD and transpose of a skinny matrix

Show: If $\mathbf{A}\in\mathbb{R}^{M\times N}$ with $M\geq N$, then there exists a matrix $\mathbf{G}$ with orthonormal rows so that $\mathbf{A}^T=\mathbf{G}\mathbf{A}\mathbf{G}$. I'm pretty lost on ...
0
votes
1answer
31 views

Deducing a formula for multiplying a tri-diagonal symmetrical matrix with vectors

This is more like a math-programming problem, dealing with memory efficiency, but I thought it would be nice to expose it here. Let $A \in \mathbb{R}^{n \times n}$ be a tri-diagonal symmetrical ...
0
votes
1answer
53 views

PageRank (power iteration method) convergence rate?

I could not get my head around the idea that the second eigenvalue is the convergence rate. Since the matrix in this application is a Markov matrix (rows/columns sum to one), the largest eigenvalue ...
1
vote
1answer
28 views

How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...
4
votes
1answer
42 views

Laplacian solvers for inversion of large matrices?

I have a large matrix L of size 400,000 $\times $ 400,000 . I'm using this L matrix in the following way. Lin = L$^{-1}$ C = D - B * Lin * B'; B,D are of appropriate sizes. L matrix is ...
0
votes
2answers
42 views

Generalized formula for sum of products.

Q:The sum of all possible products of the first n natural numbers taken two by two is? I did not understand the question as it is.What exactly is being asked?I'd really appreciate an answer ...
0
votes
0answers
16 views

Help Required in eigenvectors for sparse matrix?

I have a large sparse matrix A(~400000,~400000) . If I randomly remove few rows from the matrix will there be considerable change in the eigenvalues and the eigenvector's compared to eigenvector's of ...
0
votes
2answers
33 views

norms of Symmetric Positive Definite Submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
2
votes
2answers
35 views

Cholesky Factorization with submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
0
votes
1answer
24 views

Principal Submatrices of a Positive Definite Matrix

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
1
vote
1answer
34 views

showing condition number of a matrix is the square root of $A^T A$

For $A \in \mathbb{R}^{m\times n} : m > n, A$ has full rank, I want to show that $k(A^T A) = k(A)^2$, is there a way to do so purely from $k(A)=norm(A) norm(A^\dagger)$? Recall that $A^\dagger = ...
1
vote
0answers
35 views

Using Cholesky factorization to solve the system AXA=B

I have been given a problem of solving X, which is an unblurred image, in the system: $$B = A X A \iff X = A^{-1} B A^{-1}$$ Where the matrix A describes the blurring of an image and the matrix B is ...
2
votes
0answers
32 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...