The linear-algebra tag has no wiki summary.
3
votes
1answer
39 views
state-of-the-art bit complexity of the determinant
I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.
I would like to know what is the ...
-3
votes
1answer
52 views
the product of a matrix and a permutation matrix [closed]
Can a permutation matrix (P) be used to change the rank of another matrix (M)?
Is there any literature to this effect, or to the contrary?
I've tried a few small examples and the resulting matrix ...
2
votes
0answers
39 views
normalized tensor rank
Is there such a thing as a "normalized tensor rank" for non-square tensors (i.e. a tensor with different sizes along each mode)?
For example: If a 3rd order tensor (dimensions = 60 x 120 x 30) has ...
-1
votes
0answers
49 views
affine subspace and co-dimension
I am unable to understand the concept of affine subspace which is discussed in paper Fourier sparsity, spectral norm, and the Log-rank conjecture 2013, p 10. Lemma 19
Is affine subspace is a simply ...
10
votes
0answers
113 views
the largest element of a matrix product
Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
-1
votes
1answer
76 views
Various conjectures which is similar to Log Rank conjecture
Log rank conjecture is one of the most famous open problems in the area of communication compleixty.
Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , ...
16
votes
4answers
573 views
Checking if all products of a set of matrices eventually equal zero
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.
This means exactly what ...
6
votes
0answers
159 views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
1
vote
0answers
65 views
What is the advantage of a transformation matrix in perspective projection?
I was messing around with perspective projection. And it got me wondering whether using a perspective transformation matrix is the most efficient way. Because I also came up with another method which ...
7
votes
1answer
150 views
Why does the log-rank conjecture use rank over the reals?
In communication complexity, the log-rank conjecture states that
$$cc(M) = (\log rk(M))^{O(1)}$$
Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a ...
16
votes
4answers
516 views
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
7
votes
0answers
125 views
Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)
I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
0
votes
0answers
43 views
Is SVP in Lattices equivalent with decoding random linear codes problem in terms of hardness?
Is there any equivalence (reduction) of the Decoding of random linear codes problem which the McEliece cryptosystem is based with the SVP problem where recent lattice base cryptography put its ...
15
votes
2answers
242 views
Bigger picture behind the choice of matrices in the Strassen algorithm
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
10
votes
0answers
116 views
Complexity to compute the eigenvalue signs of the adjacency matrix
Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
5
votes
1answer
154 views
How do database aggregations form a monoid?
On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package.
The github page has some clues:
Implementations of Monoids ...
3
votes
1answer
110 views
What is this matrix column-selection problem, and how hard is it to approximate?
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place ...
1
vote
1answer
215 views
All Pairs Shortest Path - Directed graph with integer weights
I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and ...
10
votes
1answer
351 views
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space ...
2
votes
2answers
209 views
Minimizing the maximum dot product among k unit vectors in an n-dimensional space
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,
$$\alpha = \max_{1 ...
4
votes
0answers
159 views
What is computational complexity of calculating the Variance-Covariance Matrix?
I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
1
vote
0answers
99 views
Trace minimization with an orthogonality constraint
For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:
that $X$ is orthogonal.
All the matrices have real entries and $A,B$ are ...
3
votes
0answers
158 views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
8
votes
1answer
264 views
What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?
I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.
18
votes
0answers
476 views
Complexity of matrix powering
Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:
Is the top-right entry of $M^n$ positive?
Note that the ...
9
votes
1answer
155 views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
7
votes
0answers
98 views
Extension of Cheeger's inequality with distinguished vertices
The standard Cheeger's inequality for graph $G$ states that
$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$
where $\lambda$ is the second smallest eigenvalue of the normalized ...
9
votes
0answers
280 views
Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
1
vote
0answers
198 views
application for the Kchinchine inequality in Computer Science
The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has
$$
...
-5
votes
1answer
211 views
Solving a system of linear inequations
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
11
votes
1answer
251 views
Two matrices related by a permutation $B = P A P^T$ - complexity
What is computational complexity of the following problem:
given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that:
$$B = P A P^T.$$
If it helps, one ...
17
votes
2answers
500 views
Linearly independent Fourier coefficients
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...
11
votes
1answer
1k views
The computational complexity of matrix multiplication
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
9
votes
1answer
191 views
Boolean error correcting code over $\mathbb{F}_q$
Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
3
votes
0answers
69 views
Efficiently Detecting “edges” in the time frequency plane
Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local ...
2
votes
0answers
197 views
Bounding the spectral radius of a sub-stochastic matrix
Suppose that I have a "sub-stochastic" matrix, namely, for an $n\times n$ matrix $A$ with nonnegative entries such that
for any $i$, $\sum_j a_{ij}\leq 1$ and there exists some $i$ with $\sum_j ...
7
votes
1answer
400 views
Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} ...
1
vote
0answers
124 views
Complexity of checking whether linear equations have a positve solution [closed]
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution ...
3
votes
0answers
124 views
Lower Bound Methods in NonDet Communication Complexity
rank+($M$) is the minimum $r$ such that the following statement holds.
The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows.
Is rank+($M$) ...
14
votes
1answer
319 views
Complexity of deciding whether a matrix is totally regular
A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is ...
10
votes
1answer
228 views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
0
votes
0answers
114 views
norms of compressible and incompressible vector
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
2
votes
1answer
101 views
Finding mapping between two spatial representations of the same objects
I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that ...
7
votes
2answers
374 views
Midpoint solutions to linear programs
There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.
A priori, we expect the ...
9
votes
3answers
650 views
Determinant modulo m
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
1
vote
1answer
448 views
What is the significance of abstract linear algebra in machine learning/computer vision research?
I am a computer science research student working in application of Machine Learning to solve Computer Vision problems.
Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading ...
12
votes
1answer
361 views
Algorithmic Vector Problem
I have an algebraic problem related to vectors in the field GF(2).
Let $v_1, v_2, \ldots, v_m$ be (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a ...
12
votes
1answer
272 views
Log-space reduction from Parity-L to CNOT circuits?
Question.
In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it ...
10
votes
2answers
191 views
On $n$ dimensional manifolds and lattices
EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper.
I'm looking for the proof of Theorem 4 that appears in this paper:
An ...
14
votes
1answer
573 views
Solving a linear diophantine equation approximately
Consider the following problem:
Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
