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

learn more… | top users | synonyms

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 ...
2
votes
1answer
78 views

Numerically Solving a Poisson Equation with Neumann Boundary Conditions

The Problem Suppose I have an equation of the form $\nabla^2 \phi(x) = f(x)$ on the interval $A \le x \le B$, where $f(x)$ is known and $\phi(x)$ is unknown. I have Neumann-type boundary conditions: $...
1
vote
1answer
14 views

inequality in compressed sensing

Let $h\in R^n$ is a k-sparse vector, then how can i prove this inequality $$||h||_p\leq k^{1/p-1/q}||h||_q\ \ ,\forall p\in[1,q]$$ where $q\geq 1.$ please help.
0
votes
1answer
20 views

principle component analysis - manual calculation - problem finding axis and eigenvectors on approximated covariance matrix

For the sake of a future tutorial video, I'm trying to manually perform the calculation of the principle axis and associated variances. Of course i'm trying to compute the eigenvectors and ...
2
votes
0answers
57 views

Faster Cholesky factorization of $diag(\mathbf{x}_{i}) \otimes \mathbf{A} + \mathbf{B}$ for $i=1,\ldots,n$?

I have many positive integer vectors $\mathbf{x}_{i} \in \mathcal{N}^{d_1}$, $i=1,\ldots,n$, a p.s.d. matrix $\mathbf{A} \in \Re^{d_2\times d_2}$ and a p.s.d. matrix $\mathbf{B} \in \Re^{d_1d_2\times ...
2
votes
1answer
65 views

show that $\lambda_{max}(B^{-1}A) \leq 1$ (eigenvalues, matrices, preconditioning)

I'm trying to get more familiar with eigenvalues and matrices but struggle to see the following: $\lambda_{max}(B^{-1}A) \leq 1$ $A \in \mathbb{R}^{n \times n}$ is symmetric, positive definite ...
9
votes
3answers
1k views

I get a wrong determinant - why?

I'm trying to calculate the following determinant: $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ a_0 & x & a_2 & \dots & a_n \\ a_0 & a_1 & x & \dots &...
1
vote
1answer
33 views

Calculating the determinant by upper triangular reduction - can you check if it's correct?

Exercise: Calculate $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ -x & x & 0 & \dots & 0 \\ 0 & -x & x & \dots & 0 \\ \dots & \dots & \...
0
votes
0answers
16 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 $...
2
votes
1answer
61 views

Doubts on inverse power method

I found written that if matrix A is real and you use the Power method to find eigenvalues then "If the matrix and starting vector are real then the power method can never give a result with an ...
0
votes
0answers
17 views

condition number of a matrix with diagonal ones and constant else. [duplicate]

Consider the matrix $$A=\left(\begin{array}{ccccc} 1 & c & \cdots & c\\ c & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & c\\ c & \cdots & c & 1\\ \...
1
vote
1answer
111 views

Fastest way to solve linear system with block symmetric banded/Toeplitz matrix

I have a matrix of the following form: The size of the matrix may grow to be large, but the general pattern of being blockwise symmetric and banded (with 5 bands) will always hold. What is the ...
1
vote
1answer
53 views

Finding the Coefficient Matrix of a Spring-Mass System

So as part of a class in numerical linear algebra, we're exploring the topic of banded matrix system. I've come across a problem that involves Hooke's Law, but I'm having a little difficulty ...
0
votes
1answer
29 views

SVD for Seam Carving

Could SVD be used for Seam Carving ? I am making a small program for a uni course and I'm looking for different ways to calculate pixel energy; which made me come across SVD. Among others, I have ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
0
votes
1answer
32 views

How to find a number greater than the largest (smaller than the smallest) eigen value of a matrix efficiently?

I have a symmetric matrix $A$, I want to find a number say $\lambda_1$ which is greater than $\lambda$,i.e. the largest eigen value of the matrix $A$. It doesn't need to be equal to $\lambda$. But it'...
0
votes
2answers
30 views

$LU$ Factorization, improving upon stability

I was wondering when we add partial pivoting to an $LU$ factorization to a matrix $A$ it supposedly changes the data structure but improves the overall algorithm since we get better numerical ...
2
votes
0answers
30 views

Iterative methods: What happens when the spectral radius of a matrix is exactly 1?

I know that an iterative method (I'm using Jacobi and Gauss-Seidel in this case) will converge iff the spectral radius (max absolute value of eigenvalues) of its iterative matrix is strictly less than ...
1
vote
0answers
36 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
2
votes
1answer
41 views

Determining symmetricity of a matrix by multiplying with random vectors?

Stemming from an approach in a hint/answer to this question here. The idea is presented to determining wether a matrix is symmetric or not by measuring the following: $$e = \|({\bf Av})^T - ({\bf v}^...
1
vote
2answers
86 views

Is there an iterative way to evaluate least squares estimation?

Suppose to have a set of data $\{y_i, u_i\}_{i=1}^m$, where $y_i \in \mathbb{R}$ and $u_i \in \mathbb{R}^n$. The claim is that $$y_i = u_i^\top \theta + \varepsilon$$ where $\theta \in \mathbb{R}^n$...
0
votes
1answer
41 views

Prove there exist such that $A = [T]_\beta$ and $B = [T]_\gamma$ [closed]

Let $A$ and $B$ be similar $n \times n$ matrices. Prove that there exists an $n$-dimensional vector space $V$, a linear operator $T$ on $V$, and ordered bases $\beta$ and $\gamma$ for $V$ such that $A ...
1
vote
3answers
42 views

upper bound of a function $n^{1/\log(n)}$

I have the following expression $n^{1/\log(n)}, \quad where \quad n \in [1, 10,000]$. When I solve this numericall, I get the resultant value 2.718282 for all $n \in [2, 10,000]$. On this basis, I can ...
3
votes
1answer
45 views

An exercise with linear maps

I'm solving the following exercise: $\newcommand{\RR}{\mathbb{R}}$ Let $f: \RR^3 \rightarrow \RR^4: (a,b,c) \mapsto (a+2b+c, b+c, a + 2b + 3c, a + b + 2c)$ Find the basis of $f^{-1}(E)$ ...
1
vote
1answer
36 views

Choosing value of ω for SOR

I am learning about successive overrelaxation, and I'm wondering if there is an intuitive reason as to why ω must be between 0 and 2. I know that the method will not converge is ω is not on this ...
1
vote
0answers
53 views

Dynamically equivalent of numerical solution of $y' = f(y)$.

Consider an autonomous system $y' = f(y)$ and a fixed step size $h$. a) Show that the trapezoidal method applied $N$ times is equivalent to applying first half a step of forward Euler, (i.e forward ...
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 ...
1
vote
1answer
35 views

Unitary diagonalization of matrices

Can someone tell me whether every square matrix $A\in \mathbb{R}$ unitarily diagonizable? If yes what is a necessary and sufficient condition for a square matrix $A\in \mathbb{R}^{n\times n}$ to be ...
0
votes
0answers
55 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
1answer
32 views

Is there any Eigen value decomposition, which can be warm-started?

I have a Matrix, $A$ which is positive semidefinite. No consider, $B=A+\Delta$. I have Eigen decomposition of $A$ and $\Delta_{ij}<= \epsilon_1$, $\Vert \Delta \Vert_F <= \epsilon_2$. Is there ...
3
votes
1answer
66 views

$LU$ Factorization

Suppose the $A\in\mathbb{R}^{n\times n}$ is nonsingular and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^TA^{-1}e_j$,i.e., the $(i,j)$ element of $A^{-1}$ in ...
0
votes
1answer
28 views

Is it true that solving a triangular system using forward or backward substitution numerically stable?

The system is $TX = B$, where $T$ is a triangular matrix, $X$ is a unknown matrix, and $B$ is the RHS matrix. I know the system $Tx = b$ is backward stable where $b$ is a RHS vector. Detail check ...
1
vote
1answer
104 views

Best algorithm to compute the first eigenvector of symmetric matrix

Assume that we have a real symmetric matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ obtained as following : $$\mathbf{A}=\mathbf{N}-\mathbf{P},$$ with $\mathbf{N}\in\mathbb{R}^{n\times n}$ and $\mathbf{...
1
vote
0answers
37 views

Galerkin formulation of 1D linear Schrodinger equation

I am interested in the weak (Galerkin) formulation of the 1D Schrodinger equation: $i u_t−\beta u_{xx}=0$ and $u(x,0)=u_0(x)$. As usual, we do integration by parts which yields: $i (u_t,v)+\beta (...
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 ...
1
vote
1answer
54 views

Comparing matrix norm with the norm of the inverse matrix

I need help understanding and solving this problem. Prove or give a counterexample: If $A$ is a nonsingular matrix, then $\|A^{-1}\| = \|A\|^{-1}$ Is this just asking me to get the magnitude of ...
1
vote
1answer
26 views

Conditioning in regards to matrix vector product

This program involves the matrix-vector computational primitive $y \leftarrow Ax$ where $x,y\in\mathbb{R}^n$ and $A\in \mathbb{R}^{n\times n}$. A is taken to be dense and banded in the two parts of ...
1
vote
1answer
48 views

Sparse Matrix or Dense Matrix

My task is to implement the inner product and vector triad forms for a dense $A$ in single and double precision. I have successfully implemented the inner product and vector triad form although, I am ...
2
votes
1answer
39 views

Eigenvalue perturbation theory for $(A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$

Let $A, B$ be $n \times n$ matrices with full rank. I'm interested in getting a bound on how the smallest eigenvalue of $S = (A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$ changes when I perturb $A$ and $B$. ...
1
vote
1answer
34 views

Order of $LU$ factorisation

Can someone tell me how to calculate the order of a) $LU$ decomposition as well as b)the gaussian elimination of a square matrix $A$? I am at a loss ... Given:: $A$ is a $n\times n$ matrix and ...
2
votes
1answer
27 views

Finding linearly independent columns of a matrix when $m < n$

I need to a maximal set of linearly independent columns of a matrix $A$. I've googled a lot and seen various solutions, but none of them seem to work for me. What I've seen so far is 1.- Using Cauchy-...
0
votes
1answer
18 views

Efficient Row Sum of Factorized Matrix

I am currently computing the row sums of a reduced rank factored matrix by reconstructing a row subset of the original (approximated) matrix. The matrix was factored using SVD: A -> U, S, V -> U, SxV ...
1
vote
1answer
57 views

Matrix-vector product of a banded matrix

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., $\alpha_{i,i+1}...
0
votes
1answer
64 views

A generalized eigenvalue problem

The generalized eigenvalue problem likes this: $\begin{pmatrix} 0 & C_{12}\\ C_{21} & 0 \end{pmatrix} \begin{pmatrix} \xi_1\\ \xi_2 \end{pmatrix}=\rho\begin{pmatrix} C_{11} & 0\\ 0 &...
0
votes
1answer
34 views

Backward Stability Lemma

Lemma-Let $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^n$ with components, $\xi_i$ and $\eta_i$, $1\leq i\leq n$, respectively, that are floating point numbers. Computing the inner product $x^Ty$ on a ...
2
votes
1answer
84 views

In common tongue, what is the differences between sparse and dense matrices?

What are the differences with sparse and dense matrices in practice, so as to offer some insight to new learners on a more intuitive level. Obviously everyone knows about the dictionary definition of ...
0
votes
2answers
35 views

Find a spd matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = \delta_{ij}$

Let $v_1,\ldots,v_n$ be set of eigenvectors of matrix $A \in \mathbb{R}^{n\times n}$. Find a symmetric positive definte matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = \...
0
votes
1answer
47 views

$\kappa(B^{-1}A)=\kappa (AB^{-1}) = \frac{\lambda_{\max}(B^{-1}A)}{\lambda_{\min}(B^{-1}A)}$

Prove or disprove: if $A,B$ are symmetric positive definite (s.p.d.) matrices then operator 2-norm condition number $\kappa(B^{-1}A)=\kappa (AB^{-1}) = \frac{\lambda_{\max}(B^{-1}A)}{\lambda_{\min}(B^{...
0
votes
2answers
49 views

2-norm of the orthogonal projection

So far, I've deduced that if the rank of A is n, then all the columns of A are linearly independent since A has n columns. As a result, m must be greater than or equal to n. In the case that m = n, ...