Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
13 views

estimating the determinant of a large PSD matrix

Is the any property of a potentially large positive semi-definite matrix that can be leveraged on in estimating its determinant (at least in estimating if the determinant is large or small)? The ...
0
votes
1answer
33 views

Is matrix inversion stable?

As the title suggests, if I perturb the entries of an arbitrary matrix by a very small value (say increase every entry by 0.01), how different will the inversion of this perturbed matrix compared to ...
0
votes
0answers
14 views

Condition number of a matrix with factorization $A=QR$

Let $A=QR$ when $Q$ is orthogonal and R is triangular superior proof $\dfrac{1}{n}k_1(A)\leq k_1(R) \leq n k_1(A) $ and $k_2(A)=k_2(R)$ So we have for the second part $k_2(A)=||A||_2|||A^{-1}||_2$ and ...
0
votes
0answers
24 views

Example of matrices where computing the inverse is the most efficient method

I know there exists matrices where for example LU-factorization is not the most efficient way of solving the linear system of equations: $$Ax=b \tag{1}$$ Examples of such matrices are triangular or ...
0
votes
0answers
7 views

Find a matrix A with Col(A) = 1 and Ax = y and try to minimize the L0_norm of A

I need to develop a one-time trading system to match the buyers and sellers and try to minimize the number of trades. (The price is fixed so we only consider demand and supply). Suppose the total ...
0
votes
0answers
18 views

Transform an equation to get a non-negative root

I have the following equation $$f(x) = \frac{1}{\|h(x)\|_2} - \frac{1}{x} =0 \tag{1}$$ where $$h(x) = -\left[A+ x I\right]^{-1}g,\tag{2}$$ $A$ a symmetric matrix and $g$ a column vector. The initial ...
0
votes
1answer
26 views

System of equations with plus function

Let $A\in \mathbb{R}^{m\times n}$ and $b\in \mathbb{R}^m$ and $\lambda >0$. how can I solve the following system of equations? \begin{equation} A^T(Ax-b)_++\lambda x=0 \end{equation} where the plus ...
-1
votes
2answers
34 views

How to calculate this product without inverting T?

Let $T\in \mathbb{R}^{n\times n},$ which is an upper triangular matrix,and $x,y\in \mathbb R^n$. What is the most efficient way to evaluate $$x^\top T^{-2}y,$$ and what is the cost in flops? ...
1
vote
0answers
15 views

SVD of product of three matrices

Are there any library implementation tor numerical routine for SVD of product of three general matrices? I know the three matrices separately and want to avoid multiplying them directly before SVD. ...
2
votes
3answers
107 views

Solving Ax=b by FFT

I read in Wiki that it is possible to solve Ax=b via Fast Fourier Transform given that A is a circulant matrix. For example, I have $\begin{bmatrix} 1 & 0 & 0 & -1 \\ -1 & 1 & 0 &...
-1
votes
0answers
20 views

How to prove I_n - B' (AB')^{-1} A has rank-(n-m) when A,B are m-by-n, m<n? [closed]

It seems to be true that for $A,B \in \mathbb{R}^{m \times n}$, $m < n$ $ I_n - B^\top (AB^\top)^{-1} A$ has rank $(n-m)$ where $I_n$ is the $n\times n$ identity matrix. How can I prove it?
1
vote
0answers
20 views

Cross Entropy and Log Loss Relationship

I'm curious about the relationship between the Cross-Entropy function and the sum-log-loss function when doing multi-class logistic regression applied to neural networks. A setup would be as follows: ...
0
votes
1answer
31 views

Rayleigh quotient for non symmetric matrix

Suppose that we have two rectangular matrix $X\in\mathbb{R}^{n_{1}\times p}$ and $Y\in\mathbb{R}^{n_{2}\times p}$. We define $A=X^TX\in\mathbb{R}^{p\times p}$, and $B=Y^TY\in\mathbb{R}^{p\times p}$. ...
0
votes
0answers
46 views

A $3\times3$ matrix is multiplied by an unknown $3\times1$ matrix and if the result is $\mathbf{0}$ how do I compute the unknown matrix?

So my question is basically how to find the numerical values of $x_1$ $x_2$ and $x_3$ in the following equation. $$ \begin{bmatrix} -1 & -2 & -3 \\ -2 & 2 & -2 \\ 1 & 2 & 3 \\ \...
0
votes
0answers
15 views

Gauss Seidel method iteration matrix infinity norm

Let $A=D+L+U$ be a decomposition of $A$ where $D$ represents the diagonal part of $A$, $L$ represents the (strictly) lower triangular part of $A$, and $U$ be the (strictly) upper triangular part. Let $...
0
votes
1answer
16 views

magnitude of singular vectors

Calculating the SVD $A = UST$ consists of finding the eigenvalues and eigenvectors of $AA^T$ and $A^TA$. The eigenvectors of $A^TA$ make up the columns of V , the eigenvectors of $AA^T$ make up the ...
0
votes
0answers
16 views

QR algorithm of a rank deficient matrix

Let \begin{equation} A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \end{equation} Apply one iteration of the QR algorithm to $A$. The QR algorithm requires that we obtain ...
0
votes
1answer
51 views

If $A = R R^T$, prove that $||R_1 R_1^T||_2 \le ||A||_2$ where $R_1$ is first column of $R$.

I am trying to solve the following problem: For $A$ positive definite, let the Cholesky factorization be $A = R R^T$. Prove that $$\|R\|_2 \le \sqrt{\|A\|_2}$$ and that the vector $2$-norm of $R_1 ...
0
votes
0answers
29 views

Cholesky decomposition of large matrices

I am trying to obtain the Cholesky decomposition of a huge $150,000 \times 150,000$ sparse matrix with randomly distributed non-zero elements. I have only the entries for which the values are non-zero....
0
votes
0answers
20 views

How to maximize the dependent variable in a linear equation with fixed sum of independent variables?

I have a use-case where I need to use the linear equation to maximize the dependent variable ie Y in the linear equation, but the constraint is, the sum of independent variables ie xo, x1, x2, x3, x4 ...
0
votes
0answers
11 views

Subsampling from different distribution data?

I have a simple question. Thanks for helping me Is there any difference between simple random subsampling a set with uniform distribution and a set with normal distribution? How can I subsample in ...
1
vote
0answers
24 views

Sparse matrix with only $-1$ outside the diagonal

We consider a simplicial decomposition of the $n$-dimensional disk with $r$ vertices, each vertex $v_i$ is associated with a weight $w_i$ which is a positive rational number. We have a matrix equation ...
1
vote
1answer
38 views

Power method for complex Hermitian matrices

How should the power iteration be modified to handle complex yet Hermitian matrices? Because the matrix is Hermitian, the eigenvalues are real. I realize that the power method will fail if the ...
0
votes
0answers
22 views

Under or over determined linear system vs inconsistent linear system

We know the following: If there are more number of observations than that of unknowns, the linear system term as an over-determined system. If there are less number of observations than that of ...
0
votes
0answers
11 views

Questions about best square approximation

Suppose we have $\phi=span(\phi_0(x), \phi_1(x), \cdots,\phi_n(x))$, to get the best square approximation, we have to minimize $||f(x)-S^*(x)||=\int_a^b\rho(x)[f(x)-S(x)]^2dx,S^*(x) \in \phi$, then we ...
0
votes
0answers
41 views

How to quickly spot linearly dependent vectors in matrices without calculations?

I have the following matrix: $A = \begin{bmatrix} 1 &-1 & 2 \\ 2 & 1 & 0 \\ 3 & 0 & 2 \end{bmatrix}$ I clearly see that the third row is the sum of the first two rows, hence a ...
3
votes
0answers
24 views

Move eigenvalues in triangular Rayleigh quotient while keeping Krylov relation

Suppose we have the relation $$AU_k = U_kT_k + u_{k+1}b_{k+1}^H$$ Where $U_k$ is $n\times k$ and $U_k^H U_k = \text{Id}_k$, $A$ is $n\times n$, $T_k$ is upper triangular $k\times k$, $u_{k+1}$ is $n\...
0
votes
1answer
23 views

How is this error estimate for the Jacobi method derived?

If $x^{(*)}$ is the solution of a system of linear equations, the error bound for the Jacobi iteration is given by: $$ ||x^{(k)} - x^{(*)}||_\infty \leq \frac{\sigma^k}{1-\sigma}||x^{(1)}-x^{(0)}||_\...
1
vote
1answer
31 views

Questions about fixed point iteration

I am learning fixed-point iteration and am confused about the convergence rate, which is defined as follows: $$\lim_{k \rightarrow\infty}\frac{x_{k+1}-x^*}{(x_k-x^*)^p}=C,\quad C\neq 0$$ Then we call ...
0
votes
0answers
20 views

Fitting a 2D transform to a set of points

I'm digitising some hand-drawn maps. My method is to scan the map, import it into an SVG editor and trace over the features. I then mark some datum points on the SVG, with metadata to indicate that ...
0
votes
0answers
11 views

Name for this Numerical Gradient equation for 2D matrix

I am reading this paper which has the below equation: An image colour gradient is found. This is done by computing the following... $$ | \nabla r_{i,j}| ^2 = \frac{(r_{i,j} - r_{i+1,j+1}) ^ 2+ (r_{i+...
2
votes
1answer
37 views

Finding State Transition Matrix

Can someone help me compute the State Transition Matrix for the following system of linear differential equations? $$\vec x=\begin{bmatrix}2 & -t\\-t & 2\end{bmatrix} \vec x$$ My attempt: ...
0
votes
1answer
47 views

Finding spectral radius of matrix without computing characteristic polynomial

Let $$A=\begin{pmatrix}3&1&1\\1&2&1\\0&1&2\end{pmatrix}.$$ I am asked to find its spectral radius, i.e., $$\rho(A) = \max \left\{ |\lambda| : \lambda \text{ eigenvalue of }A \...
1
vote
1answer
35 views

Approximate $f(x)= x^2$ with the best approximation in $L_1$ under the given norm.

The given norm is: $||f||= \sqrt{A_0 |f(x_0)|^2 + A_1 |f(x_1)|^2 + A_2 |f(x_2)|^2}$ And from a previous question I have found the following: $A_0 = \frac {-\sqrt{\pi/3}}{2}$ $A_1 = \frac {\sqrt{\pi/3}}...
1
vote
1answer
38 views

Simultaneous orthogonalization in Arnoldi iteration

Recently, I was studying Stewart's A Krylov-Schur Algorithm for Large Eigenproblems. After a survey, the so called expansion phase is implemented, with the description given below: For the sake of ...
0
votes
1answer
55 views

How to solver the least square problem involves with the variable is the product of Hadamard Product?

I encounted an least square problem involves hadamard product of two $100\times 1$ matrix: X, Y: $$ A_{N\times100}*(X_{100\times 1}∘Y_{100\times 1})_{100\times 1} = B_{N\times 1} $$ In above equation,...
0
votes
0answers
23 views

Expressing the spectral radius as a function of the matrix size

Currently, I am working with a (non-symmetric) discretization matrix $A$ coming from a convection-diffusion problem without elimination of boundary conditions. Regarding the SOR algorithm, I have to ...
0
votes
1answer
34 views

Show that spectral radius is $\rho(M^{-1}K)\ge1$

Given a splitting of symmetric singular matrix by A=M-K where M is nonsingular. Show that spectral radius of $\rho(M^{-1}K)\ge1$. Recall spectral radius is $\rho(A)=\max_i|\lambda_i|$ Hint: any zero ...
2
votes
0answers
22 views

Are Python/MATLAB/Mathematica numerical eigenvectors affected by eigenvalue degeneracies outside region of calculation?

I have a discretized 2D mesh over which I calculate eigenvalues and eigenvectors of some Hermitian 2 x 2 matrix at each point along a closed loop parameterized by parameter t. The eigenvectors are ...
0
votes
1answer
46 views

Solving some special linear system

Assuming we have some matrix $A\in \mathbb C^{m\times m}$ with $n\leq m$ of full rank and there are some vectors $q,b\in \mathbb C^m$. We are now trying to solve the following system $$\left(\begin{...
0
votes
1answer
44 views

Is there a way to rewrite this matrix equation to eliminate inverse matrix?

Let $\mathbf{u},\mathbf{v}\in\mathbb{R}^{n}$ and $\mathbf{K}\in\operatorname{GL}(n)$. Consider the following constraint: $$\mathbf{u}^{\top} \left( \mathbf{K^{\top} K} \right)^{-1} \mathbf{v} = 0 \tag{...
0
votes
0answers
30 views

How to determine the eigenvalues and eigenvector of the Householder matrix

Here is the specification again: Let $ w \in \mathbb{R}^{n} $ and $||w||=1$. The $n \times n$- matrix. $$ P:=I-2ww^t $$ is called the Householder transform and $w$ is called the Householder vector. ...
1
vote
0answers
20 views

Finding the projection of a cycle polygon with maximum area and no intersections

Given a polygon (forming a loop) embedded in euclidean space of dimension 3 or higher, how to find the 2d projection maximizing its area and such that it doesn't intersect ? My initial idea was to ...
0
votes
1answer
35 views

Some questions about well condition of a problem

Considerer the matrix $A \in \mathbb{R}^{n\times n}$ and the system $Ax=b$ with $b=(1,1)$ find an upper bound of $||\delta_x||_\infty/||x||_\infty$ in terms of $||\delta_b||_\infty/||b||_\infty$, with ...
1
vote
1answer
61 views

For what $x$ does the function $g(x) = \frac{x^2+a}{2x}$ converge to fixed point $\sqrt{a}$

What is the interval where the function converges to this fixed point? So we have a function $$g(x) = \frac{x^2+a}{2x}$$ We want to know the interval where this function for sure converges to fixed ...
1
vote
0answers
33 views

Projection with a (diagonally) modified metric

$ %%% NOTATIONS % sets \def\N{\mathbb{N}} \def\R{\mathbb{R}} \def\PPP{\mathbb{P}} \def\EE{\mathbb{E}} \def\SS{\mathbb{S}} \def\SSS{{\mathbb{S}^{p-1}}} \def\uno{\mathbb{1}} \def\AA{\mathcal{A}} \def\BB{...
3
votes
1answer
65 views

Finding eigenvalues of a large matrix close to a given value

In an address from 1997, Carl Cowen said: [I]n 1974, a graduate student friend studying civil engineering and working on modeling vibrations in buildings caused by earthquakes asked me how he could ...
0
votes
1answer
70 views

Computing the square root of complex number in a stable manner

The square root $\pm(u+iv)$ of a complex number $x+iv$ with $y\neq0$ may be calculated from the formulas $u=\pm\sqrt{\frac{x+\sqrt{x^2+y^2}}{2}}$ $v=\frac{y}{2u}$ compare the cases $x\geq0$ and $x<...
0
votes
0answers
15 views

Find a basis for $S(1,0)h[a,b]=\{p∈C0[a,b],p|Ii∈P1(Ii)\}$

On the intervall $[a,b]$ let $a = x_o< x_1 < x_2 < ... < x_n = b$ be a decomposition. Consider the Vectorspace of the piecewise linear functions $$S_h^{(1,0)}[a,b] = \{p \in C^0[a,b], p|_{{...
0
votes
0answers
37 views

Uniquness of a QR-Decomposition: Show that there exists an orthogonal diagonal matrix $ S \in \mathbb{R}^{n \times n} $

Let $ A=Q_{1} R_{1}=Q_{2} R_{2} $ be two $ Q R $-decompositions of a quadratic matrix $A \in \mathbb{R}^{n \times n} $ with full rank, i.e., $ \operatorname{rank}(A)=n $. This means $ Q_{1}, Q_{2} \in ...

1
2 3 4 5
63