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

learn more… | top users | synonyms

1
vote
0answers
351 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
376 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $$F(x) = \sum_{i=1}^{M}\left\|x_{i+1} - x_i - K\left(\frac{x_{i+1} + x_i}{2}\right)\right\|^2 + \|x_1-c_1\|^2 + \|x_N-c_2\|^2,$$ where $x$ is a vector of $N$ scalars, ...
1
vote
0answers
103 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!
1
vote
0answers
56 views

formulas for exact values of singular values in low dimension?

Are there formulas for the singular values of a real matrix in low dimension, i.e. for a $2 \times 2$ matrix or a $2 \times 3$ matrix? Any comment is welcome.
1
vote
0answers
158 views

The fastest algorithm of computing Principal eigenvector of a non-negative-entries matrix

I am studying the QR algorithm, is it the fastest one in this situation?
1
vote
0answers
169 views

Stable and efficient projection onto subspace along another subspace

Suppose we are given the euclidean space $\mathbb R^{n+m}$ with the decompositin $\mathbb R^n = V \oplus W$, which we however do not expect to be orthogonal. Let us describe the matrix $P$ that ...
1
vote
0answers
168 views

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
0answers
76 views

Looking for a specific paper not available electronically

not really sure that it is the right place to post, but I'll give it a go. I really would love to have a look to this technical report J.G. Lewis, Algorithms for Sparse Matrix Eigenvalue Problems, ...
1
vote
0answers
107 views

Fast simultaneous orthonormal basis computation for multiple nullspaces

Consider vectors $a_i\in R^{m\times n}$ and $B\in R^{m\times p}$, with $n +p < m$, and assume that the columns of $(A, B)$ are linearly independent. To compute an orthobasis for $\text{ker}(A)$, it ...
1
vote
0answers
492 views

Tridiagonal sparse matrix - linear equation

I have to following linear system to solve : $Ax=e_1$ where $A$ is a sparse tridiagonal matrix with the main diagonal terms $a_{ii}$ being all different, and the off-diagonal terms being each others ...
0
votes
0answers
16 views

Schur complement of a matrix $A$

Let $A\in\mathbb{R}^{n\times n}$ and its inverse be partitioned $$A = \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22}\\ \end{pmatrix},\:\: A^{-1} = \begin{pmatrix} \tilde{A_{22}} & ...
0
votes
0answers
9 views

Computing $PAQ = LU$ using Gaussian elimination with complete pivoting

Suppose $PAQ = LU$ is computed via Gaussian elimination with complete pivoting. Show that there is no element in $e_i^{T}U$ i.e., row $i$ of $U$, whose magnitude is larger than $|\mu_{ii}| = ...
0
votes
0answers
39 views

Numerical method for solving equation with $u \frac{\mathrm{d}u}{\mathrm{d}x} + u$

I'm looking for a finite difference method to solve $$a(x) u \frac{\mathrm{d}u}{\mathrm{d}x} + u = b(x)$$ where $u(0) = c$. I tried to do a lagging convergence on the $u$ ie $$a(x) u^{(n)} ...
0
votes
0answers
16 views

Gauss Seidel - Finite Element Method

I am solving an equation using finite element method, and for that I have to use Gauss Seidel to invert a matrix. In Gauss Seidel I am using a "while" which breaks if the absolute error reaches the ...
0
votes
0answers
7 views

Determine an efficient algorithm and describe the computational/storage complexity

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in ...
0
votes
0answers
23 views

absolute value matrix and derivation of A^1 b

I have a question who could I solve the following sentence? Given is the vector $\vec{b} \in \mathbb{R^n}$ and the function $f : GL(n,\mathbb{R}) \to \mathbb{R}^n$ with $f(A) = A^{-1}b$. Then ...
0
votes
0answers
23 views

Compute the condition number of the matrix and show for what $\Delta x$ it is singular

Given the laplacian $N \times N$ matrix \begin{align*} A=\frac{1}{(\Delta x)^2}\begin{pmatrix} 2&-1& & &\\ -1&2&-1& &\\ &\ddots&\ddots&\ddots&\\ ...
0
votes
0answers
9 views

Determinants using Row Reduction replacement

I am aware replacement does not affect the value of determinant when doing a row reduction. However, I realised there isn't a good explanation on how to handle different forms of replacement when ...
0
votes
0answers
20 views

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$?

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$, where $|T| =|[T_{ij}]| = [|T_{ij}|]$ ?
0
votes
0answers
10 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve ...
0
votes
0answers
25 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use ...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system ...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
0
votes
0answers
12 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
14 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m ...
0
votes
0answers
17 views

question about dimensions.

$A\in\mathbb{R}^{n\times n}$, when solving $Ax=b$ numerically in projection method, we approximate the exact solution $x^*$ by $y$ in the subspace $K$ which has the dimension $m$. my textbook said ...
0
votes
0answers
23 views

Applications of Khatri-Rao matrices

I'm interested in what applications there are for Khatri-Rao matrices, and in particular for solving linear systems of equations involving Khatri-Rao matrices. A Khatri-Rao matrix is a block matrix ...
0
votes
0answers
17 views

Why does biconjugate gradient (BiCG) work for nonsymmetric matrices?

After looking through the derivation of CG, I understand why it requires the coefficient matrix $A$ to be symmetric, since the property is used to produce a short recurrence relation for the ...
0
votes
0answers
27 views

Simplifying matrix expressions with LU decomposition?

If $A, B, C$ are $n \times n$ matrices, with $B$ and $C$ nonsingular, and $b$ is a vector of size $n$, how could one determine $$x = B^{-1}(2A + I)(C^{−1} + A)b?$$ I assume the solution has to do with ...
0
votes
0answers
27 views

Is $ \| \sum_{i \in [k]} \otimes^3 v_i - T \|_F^2 + \theta \| \sum_{i \in [k]} \otimes^3 v_i \|_F^2$ convex?

I am trying to find the minima of the following equation with respect to $v_i$, $i \in [k]$, to solve an optimization problem but I can't manage to make (stochastic or not stochastic, neither of them) ...
0
votes
0answers
49 views

Prove Norm Theorems

I have the following as given: Let $A \in C^{m\times m}$. Then: 1) $$\lVert A\rVert_1 =\sup_{v\in C^m \setminus\{0\} }{\lVert A_v\rVert_1 \over \lVert v\rVert_1} = \max_{j} \sum_i |a_{ij}|$$ How can ...
0
votes
0answers
15 views

Minimising two interdependent equations with least squares regression.

Originally, I had a set of points in three dimensional space that I was fitting using linear regression. So my model is $$Y = \alpha A+ \beta B$$ where $Y = \{y_i\}$ is the dependent variable, and ...
0
votes
0answers
12 views

matrix optimization problem techniques

I'm looking for some resources on learning techniques commonly used in matrix optimization. For example, minimization of the Frobenius/nuclear/weighted norm of a function of a matrix subject to ...
0
votes
0answers
46 views

Beginner Linear Algebra 1 equation with 3 variables

I do not understand what to put into the remaining values. I tried to solve for the y and z like I did for the x, but the system is telling me that is incorrect. Some help would be appreciated
0
votes
0answers
25 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...
0
votes
0answers
33 views

Hilbert Matrix, Gaussian Elimination with varying pivot strategies, and computation error.

I'm doing a project for my Numerical Analysis class about computational error related to Gaussian elimination, gaussian elimination with partial pivoting, and gaussian elimination with scaled partial ...
0
votes
0answers
23 views

Matrix approximation

How to solve numerically for non-negative full-rank matrices $P$ and $E$ with the following constraints? $Y$ is a known non-negative matrix with $G$ rows and $N$ columns, $G > N$ 1) ...
0
votes
0answers
27 views

Cholesky update of $A'A+\gamma I$

Let $A$ be such that $A'A$ is positive definite and admits the Cholesky factorisation $$ A'A = LL' $$ Let us append a column-vector $c$ in $A$ and define $$\bar{A}=\begin{bmatrix}A & ...
0
votes
0answers
63 views

Sum of squares of eigenvalues

Let $\Lambda(A)$ be the sequence of eigenvalues including repeated eigenvalues, if there exist. Show that $$\inf_{X\mbox{ not singular }} \lVert X^{-1}AX\rVert_F^2=\sum_{\lambda\in \Lambda(A)} ...
0
votes
0answers
52 views

LU decomposition with pivot

I'm trying to LU decompose, with pivoting, the following matrix ($A=(a_{ij})$): A = [2 1 2; 1 0 3; 4 -3 -1]; % matlab I cannot make out from my literature ...
0
votes
0answers
31 views

Inverted pendelum Matrix numerical derivative

Here I've written a dynamic function as : ...
0
votes
0answers
41 views

Way to verify a least-squares solution without actually solving for $x$ and $y$?

I just found the least squares solution of the system $\mathbf{x}A = \mathbf{b} = \begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} 3 & 2 & 1 \\ 2 & 3 & 2\end{pmatrix} = ...
0
votes
0answers
43 views

roots of Padé approximating polynomials to the exponential function

I need to obtain (numerically) the roots of the denominator in the Padé approximation to the exponential function $e^{-x}$, in Python. I can calculate its coefficients in closed form (see below). But ...
0
votes
0answers
33 views

Find a symmetric matrix of minimal Frobenius norm

Let $A\in \mathbb{R}^{n\times n}$ be a symmetric matrix, And let $$x\in \mathbb{R}^n$$ be such that $\lVert Ax-b\rVert_2 = \min_{z\in \mathbb{R}^n} \lVert Az-b\rVert_2$. Show how to calculate a ...
0
votes
0answers
27 views

Handling large exponents in a matrix

I have four quantities stemming from a 4th order differential equation. I can represent these as a vector which is a product of a 4X4 matrix $$ M=\left\{v,\frac{\partial v}{\partial x},\frac{\partial ...
0
votes
0answers
19 views

Cutting an Orthonormal Basis

I have constructed an orthonormal basis $\{\mathbf{q_1},\dots,\mathbf{q_n}\}$ for a Krylov set $\mathcal{S}_n(A,\mathbf{x})= \text{span}\{\mathbf{x},A\mathbf{x},\dots,A^{n-1}\mathbf{x}\}$ with ...
0
votes
0answers
25 views

Relation of the upper triangular factor and the original matrix

Suppose $$PA = LU$$ is the LU factorization(exact) of the square real matrix A, L is the unit lower triangular matrix. Is there a way to determine the relation between the norm of $U$ and the norm ...
0
votes
0answers
27 views

Why does the Lanczos algorithm make an orthonormal basis for the Krylov subspace?

Starting with a $v_0$= $b_0$=0 and a symmetric positive definite matrix A. Why does the following algorithm forms an orthonormal basis span{$v_1$,$v_2$,...,$v_n$} for $K_n$(A,$v_1$)? for k=1,...,n-1 ...
0
votes
0answers
59 views

Damped Iteration

For splitting $A = M-P$ a damped iteration with damping factor $\gamma <1$ and scalar $\omega$ is $$x^{k+1} = x^{k} +\gamma M^{-1}r^{k}$$ where $$r^{k} = b-Ax^{k}$$ $$M =\frac{1}{\omega }I $$ $$P = ...