Questions tagged [matrix]

Matrix is a rectangular array of elements (e.q. numbers, symbols, or expressions), arranged in columns and rows.

Filter by
Sorted by
Tagged with
1
vote
2answers
2k views

Gram-Schmidt method to identify linearly dependent vectors

A method to orthogonalize a set of vectors (vectors of unit length that are mutually orthogonal) is the Gram-Schmidt process: http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process Note that the ...
2
votes
3answers
940 views

Convergence of the gradient descent and linear vs non-linear fixed point iteration

Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can ...
28
votes
4answers
16k views

Dealing with the inverse of a positive definite symmetric (covariance) matrix?

In statistics and its various applications, we often calculate the covariance matrix, which is positive definite (in the cases considered) and symmetric, for various uses. Sometimes, we need the ...
8
votes
1answer
169 views

Sudden drops in matrix multiplication performance

I've been reading about implementing dense matrix multiplication when the matrix doesn't fit in cache. One of the graphs I've seen (slide 9 from these slides) shows sudden drops in performance using ...
5
votes
1answer
160 views

Is there a way to inspect the graph of a sparse matrix with PETSc?

I am currently trying to code the CA-CG method within the PETSc framework. A mandatory step in this process is the implementation of the "matrix powers kernel" algorithm for a generic sparse matrix. ...
2
votes
1answer
185 views

Root Convergence rate of Iterative Scheme

I have an iterative sequence for optimizing an EM (Expectation Maximization) algorithm based loss function $L(X)$ with $t$ being the iteration number as: $X_t=ABX_{t-1}+CX_{t-1}+X_{t-1}$ where $A$ is ...
2
votes
3answers
405 views

derivative of linsolve

Consider a vector $\mathbf{g} \in \mathbb{R}^{m}$ and a matrix $\mathbf{A} \equiv \mathbf{A(g)} \in \mathcal{M}_{p\times q} [\mathbb{R}]$, a function of $\mathbf{g}$. Furthermore, let $\mathbf{S} \...
3
votes
1answer
126 views

Calculation of Multivariate Coherence

I trying to detecting whether a data set of time series has a global change in frequencies. Calculating the average (or median) pairwise coherence, I feel, misses the point because I am trying to get ...
3
votes
1answer
93 views

High-dimensional representation of arbitrary input

Given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ with positive entries and zero diagonal, is it always possible to construct a high-dimensional configuration in Euclidean space, such that these ...
3
votes
2answers
246 views

Positive semi-definiteness of a (symmetric) matrix

Suppose a matrix $A\in\mathbb{R}^{n\times n}$ is given. Faced with a proof for $$x^TAx>0,$$ for a non-zero vector $x\in\mathbb{R}^{n}$, I was thinking to use the information of the spectrum of $A$ (...
2
votes
2answers
128 views

Handling inconsistent solutions obtained by PCA

In order to achieve a 2D representation $X\in\mathbb{R}^{n\times 2}$ of some high-dimensional data residing in $Y\in\mathbb{R}^{n\times k}$, I use PCA:$$X=Y\cdot U,$$where $U\in\mathbb{R}^{k\times 2}$ ...
1
vote
1answer
83 views

Normalizing axes prior to PCA

For a given centered configuration of points $X\in\mathbb{R}^{n\times 3}$, the covariance matrix is denoted by $S=\frac{1}{n}X^TX$. Recall that the 2D PCA solution is obtained by $Y=X\cdot U$, where $...
0
votes
1answer
71 views

Relation to all-pairs Euclidean distances

Given $d$-dimensional coordinates residing in a matrix $X\in\mathbb{R}^{n\times d}$, the Euclidean distance between items $i$ and $j$ is denoted as $g_{ij}$. Let $c\in\mathbb{R}^d$ denote the centroid ...
17
votes
5answers
6k views

What is the best way to determine the number of non zeros in sparse matrix multiplication?

I was wondering whether there is a fast and efficient method to find the number of non zeros in advance for sparse matrix multiplication operation assuming both matrices are in CSC or CSR format. I ...
1
vote
2answers
1k views

What does “Counting algebraic multiplicity” mean?

As stated in the title, I encountered a proof with the final statement of the form "the eigenvalues of A are then $\{\lambda_1+c, \lambda_2, \dots, \lambda_n \},$ counting algebraic multiplicity. ...
0
votes
1answer
283 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
2
votes
2answers
120 views

A sufficient number of distances to recover relative positions of n points

On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space. For instance, work from http://www.dimitris-...
11
votes
3answers
1k views

Libraries for solving Lyapunov's equation

The following matrix equation $$B\Sigma + \Sigma B^T + C = 0$$ in $\Sigma$ $-$ for given $B$ and $C$ matrices $-$ appears in my work as a characterization of a covariance matrix. I have learned that ...
3
votes
2answers
308 views

Computing Permanents of $64 \times 64$ Matrices

I need to compute the Matrix Permanents of several $64 \times 64$, zero-one matrices. I have tried using the built in functions in both Sage and Maple, but both programs return out of memory errors. I ...
13
votes
3answers
4k views

Single versus double floating-point precision

Single precision floating point numbers take up half the memory and on modern machines (even on GPUs it seems) operations can be done with them at almost twice the speed compared to double precision. ...
7
votes
3answers
245 views

Wanting to learn about matrix solvers

Edit: I was advised to replace the question with a more specific one. Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will ...
6
votes
2answers
271 views

Derive PCA with SVD

The context is I have a big matrix, 20K * 50K, and I want reduce the dimensionality. In R, it's impossible to apply PCA with more variables(columns) than observations(rows). Therefore, I am trying a ...
4
votes
2answers
78 views

Any reference which summarizes decompositions?

Is there any reference (preferably available online as PDF, Free would be best) which summarizes the various matrix decomposition with their conditions for use, usage, algorithm, complexity and ...
5
votes
2answers
270 views

Out-of-core matrix transpose of row compressed data

Summary: Are there good algorithms for out-of-core dense matrix transpose if each row of the matrix is separately compressed? Details: The matrix is about 1 TB uncompressed, and is roughly but not ...
3
votes
1answer
1k views

Application of an orthogonal matrix to a 3D configuration of point

Suppose a 3D configuration of points is given, $X\in\mathbb{R}^{n\times 3}$, and a matrix $Q\in\mathbb{3\times 2}$, with orthonormal columns. Now, suppose a mapping to 2D is obtained as $$Y=XQ.$$ ...
10
votes
3answers
5k views

MATLAB matrix multiplication (the best computational approach)

I have to make a coordinates transformation between two reference systems (axes). For that, three matrices ($3\times3$) have to be multiplied due to some intermediate axes being used. I have thought ...
2
votes
1answer
345 views

In Octave, how do I specify that the solution to a matrix equation should be over integers?

In Octave, how do I specify that the solution to a matrix equation should be over integers? I.e., Given matrix $A$, vectors $x$ and $b$; $Ax=b$. Find vector $x=A^{-1}b$ such that all its entries are ...
5
votes
1answer
195 views

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc?

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc? Also, where can I find more information on each of the MatTypes? I went to the MatType documentation, but it didn't have anything but ...
3
votes
1answer
228 views

3D to 2D projections, a generalization

Given some data points in 3D, $X\in\mathbb{R}^{n\times 3}$, could one say that $$Y=XP,$$ for some $P\in\mathbb{R}^{3\times 2}$ actually corresponds to a particular viewpoint on a 3D data? Basically, ...
4
votes
2answers
153 views

Simplifying some operations on Gram matrices

Suppose two Gram matrices are given $A, B\in\mathbb{R}^{n\times n}$, such that $$A=XX^T,~~~~~~~~~~~~~B=YY^T,$$ for some $X, Y\in\mathbb{R}^{n\times k}$, $k\ll n$. Also, suppose a Gram matrix based on ...
11
votes
1answer
700 views

Projecting out the null-space of $A$ from $b$ in $Ax=b$

Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
4
votes
1answer
129 views

Constructing the origin position by transforming distance information

Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from ...
11
votes
4answers
2k views

Finding the square root of a Laplacian matrix

Suppose the following matrix $A$ is given $$ \left[\begin{array}{ccc} 0.500 & -0.333 & -0.167\\ -0.500 & 0.667 & -0.167\\ -0.500 & -0.333 & 0.833\end{array}\right]$$ with ...
4
votes
0answers
625 views

Perron-Frobenius theorem on general real symmetric matrices

From the Perron-Frobenius theorem, it might be concluded that the spectral radius is the largest eigenvalue for positive matrices, ie, matrices with strictly positive entries. In other words, the ...
16
votes
4answers
2k views

Why can't Householder reflections diagonalize a matrix?

When computing the QR factorization in practice, one uses Householder reflections to zero out the lower portion of a matrix. I know that for computing eigenvalues of symmetric matrices, the best you ...
3
votes
0answers
69 views

Understanding how Numpy does SVD [duplicate]

Possible Duplicate: Understanding how Numpy does SVD I have been using different methods to calculate both the rank of a matrix and the solution of a matrix system of equations. I came across the ...
2
votes
1answer
225 views

Proof continuation for rigid transformation on PCA solution

Suppose a matrix $X\in\mathbb{R}^{n\times 3}$ is given as a Principal Component Analysis (PCA) projection from some high dimensional space. The 2D PCA solution on X, say $Y\in\mathbb{R}^{n\times 2}$ ...
7
votes
3answers
8k views

Gershgorin Circle Theorem to estimate the eigenvalues

In order to estimate the eigenvalues of a real symmetric $n\times n$ matrix, I intend to use the Gershgorin Circle Theorem. Unfortunately, the examples one might find on the internet are a bit ...
1
vote
3answers
245 views

Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (...
0
votes
1answer
978 views

A Comparison between GMRES, QMR and LU for Dense Matrices

As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU. Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is ...
15
votes
3answers
2k views

Why isn't my Matrix-Vector Multiplication Scaling?

Sorry for the long post but I wanted to include everything that I thought was relevant in the first go. What I want I am implementing a parallel version of Krylov Subspace Methods for Dense Matrices....
3
votes
2answers
122 views

Time-stable SO(n) matrix synthesis algorithm

Consider an equation $S(t)b(t) = a$, where $a, b(t) \in S^{n-1}$ are given and the vector $b(t)$ is continuous, i.e. its endpoint traces a continuous curve on the unit sphere. The task is to find ...
3
votes
1answer
878 views

Spectral decomposition with eigenvalue shift

Suppose a square, real and symmetric matrix $G\in\mathbb{R}^{n\times n}$ is given, and it is known to have one zero eigenvalue associated with all ones eigenvector, $1_n$. I'm aware that the (possibly)...
12
votes
3answers
2k views

What's the current state of the art regarding algorithms for the singular value decomposition?

I'm working on a header-only matrix library to provide some reasonable degree of linear algebra capability in as simple a package as possible, and I'm trying to survey what the current state of the ...
12
votes
1answer
2k views

weighted SVD problem?

Given two matrices $A$ and $B$, I'd like to find vectors $x$ and $y$, such that, $$ \min \sum_{ij} (A_{ij} - x_i y_j B_{ij})^2. $$ In matrix form, I'm trying to minimize the Frobenius norm of $A - \...
4
votes
2answers
5k views

Is there an MPI All Gather operation for matrices?

I have a distributed matrix, in block column format. I know that I can reshape the matrix into one long vector and use an all_gatherv operation. I just wanted to avoid the trouble of having to ...
9
votes
2answers
1k views

Safe application of iterative methods on diagonally dominant matrices

Suppose the following linear system is given $$Lx=c,\tag1$$ where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
4
votes
4answers
228 views

Determining the algorithmic complexity

A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
7
votes
1answer
587 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
4
votes
3answers
219 views

Efficiently computing a few localized eigenvectors

Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$. The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...

1 7 8 9 10 11