# Tagged Questions

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

29 views

### Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
92 views

### Algorithms for computing matrix logarithm.

On my quest to find the holy grail of mathematics become a little bit better at algebra, I have read up on matrix logarithms and exponentials and how useful they can be in investigating groups and ...
39 views

### Equaity of two norms of matrix

I have to prove that if A is a $n \times k$ matrix and $A^H$ the hermitian matrix of A, $||A||_2=||A^H||_2$. Where $||A||_2=\sup\{ ||Ax||: ||x||\leq 1\}$ and $|| \cdot ||$ is the euclidean nrmm of ...
43 views

### equality of norms

I have to show that $\| A\|_2=\sqrt{\| A^H\times A\|_2}$. $A$ is a $n\times k$ matrix, $\| \cdot \|_2$ is defined as : $$\| A\|_2=\sup\{ \|Ax\|, \|x\|\leq 1 \}$$ and $\| \cdot \|$ is the ...
37 views

### A proof of the uniqueness of svd?

I understand the geometric intuition, but the proof by induction in Trefethen book confuses me : it seems to me that a 1*1 complex matrix has infinitely many left and right singular vector pairs? ...
38 views

673 views

### Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems

I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) : Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear ...
33 views

### Stability of (floating point) computed variance

Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33: So every time we store an number and do a operation, we introduce an error bounded ...
29 views

### What are some possible reasons for a large condition number?

For this question, please assume that I am talking about the condition number with respect to the spectral norm. That is, $\kappa_2(A) = \|A\|_2\|A^{-1}\|_2 = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$. ...
12 views

### Proof of QR Algoirthm Convergence

I am reading Trefthen and Bau and the amount of implicit proof steps are killing me. Can someone explain how the statement of convergence for the "pure" QR Eigenvalue Algorithm (Theorem 28.1) is ...
23 views

### how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
37 views

### Parametrization of the $Ax=b, x \geq 0$ domain for Monte-Carlo simulation

I have a linear system, $n=15$, with $6$ constraints. There's no problem finding a single solution or establishing the null space; so I can see the full solution space. But I'm only interested in ...
12 views

### Linear Relationship of two equations

if $0.46a = 120b$ and $2.68a = 60b$ The relationship is linear. what does $0b$ equal in terms of $a$? what does $1b$ equal in terms of $a$? A method to work this out would also be nice, I have ...
28 views

### Gauss Seidel Iteration for a specific matrix

We seek to solve $Au= f$ via iteration, where $$A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right )$$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the ...
63 views

223 views

### Product rule in discrete derivative in finite difference scheme.

Suppose we are on real line and I want to discretize the usual derivative operator. Take a smooth function $u$ and step size $h$. Then I could define $$\Delta_+u(i) = \frac{u(i+1)-u(i)}{h}$$ as the ...
55 views

### Linear combination of basis function in logarithm space. Is it possible?

I have a function $f(x)$. As theory said that it can represent by linear combination of basis functions such as $$f(x)=\sum_{i=1}^{N}\alpha_ig_i(x)$$ where $\alpha$ is coefficient and $g(.)$ is basis ...
26 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 ...
34 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 ...
88 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 ...
60 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 ...
85 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 ...
38 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 ...
288 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: $$\nabla^2 \; u(r,\theta) \;=\; f(r,\theta)$$ The boundary conditions:...
119 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 ...
62 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 $\hat{R}$...
46 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: ...
58 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. ...
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 ...
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}$ ...