Questions tagged [rank]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
13
votes
4answers
256 views

Rapidly determining whether or not a dense matrix is of low rank

In a software project that I'm working on, certain computations are vastly easier for dense low-rank matrices. Some problem instances involve dense low-rank matrices, but they're given to me in full, ...
7
votes
3answers
1k views

How to compute the rank of a large sparse matrix in MATLAB

I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to ...
4
votes
2answers
993 views

Computational complexity and implementation of UDU Modified Cholesky Rank 1 Update

I am attempting to increase the performance of a legacy Kalman Filter implementation. The state covariance is factored in terms of UDU, i.e. $\mathbf{P} = \mathbf{U}\mathbf{D}\mathbf{U}^T$. Many ...
3
votes
2answers
462 views

Quadratic programs with rank deficient positive semidefinite matrices

Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
2
votes
1answer
123 views

Minimize the number of unique elements in a vector

I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
2
votes
2answers
1k views

Writing Real Symmetric Matrices as Linear Combination of Rank One Symmetric Terms $uu^T$

Given a real symmetric matrix $M$, ostensibly of "low rank", efficiently find an expression $M = \sum \alpha_i u_i u_i^T$ using the number of terms rank($M$). A 2011 StackOverflow Question Dense ...
2
votes
1answer
57 views

Rank of Hadamard Product with Masked Matrix

I have a matrix $A\in\{0,1\}^{d\times n}$ and $rank(A)=d,d<n$, and another matrix $X\in \mathbb{R}^{d\times n}$, but I do not know the rank of $X$. What can we say about the rank of their Hadamard ...
1
vote
1answer
164 views

Fast counting of all submatrices of a binary matrix with a full column rank

I have a binary full-rank matrix of size, say, $25 \times 50$. I need to count how many subsets of its columns form matrices with a full column rank, i.e. all the columns in the subset are linearly ...
1
vote
0answers
145 views

Rank filter on an nXm array using python

I would like to apply a rank filter on an nXm numpy array. Let's say I have this array: ...
1
vote
1answer
154 views

Matrix Decomposition of Conics

I was reading about ellipse-ellipse intersection and I came across this article: https://math.stackexchange.com/questions/679622/intersection-between-conic-and-line-in-homogeneous-space/867428#...
1
vote
0answers
79 views

Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
0
votes
1answer
77 views

Rank of image intensity matrix

I've been reading a paper about using Matrix Completion for Photometric Stereo but I am having some troubles in section 2.2 trying to understand why irrespective of the number of pixels and the number ...
0
votes
1answer
196 views

Diagonalize a circulant-plus-rank-one matrix

Suppose $A=uv^T$ where $u$ and $v$ are non-zero column vectors in $\mathbb{R}^n, n\geq 3$. $\lambda=0$ is an eigenvalue of $A$ since $A$ is not of full rank. $\lambda=v^Tu$ is also an eigenvalue of $A$...