Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

Filter by
Sorted by
Tagged with
2
votes
1answer
74 views

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
1
vote
0answers
23 views

Reference showing global optimality of local minima for matrix factorization

Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized. I have heard it ...
1
vote
0answers
59 views

Smallest nonzero eigenvalue of a sum of +1/-1 rank-one matrices?

Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\...
1
vote
0answers
92 views

Is this proof of $LP$ being in $coNP$ correct?

I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there ...
3
votes
0answers
61 views

Precise rank of a sparse integer matrix

Consider a large sparse rectangular integer matrix. Is there a way to compute its exact rank that is better in terms of speed and/or memory usage compared to a dense matrix?
2
votes
1answer
112 views

Solver for uniform matroid isomorphism

I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), ...
3
votes
1answer
223 views

An optimization problem

I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$ maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
11
votes
2answers
3k views

Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
3
votes
1answer
54 views

Problem conditions to use Laplacian solvers

I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense. Suppose that we want to solve Ax=b, ...
0
votes
0answers
24 views

Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector [duplicate]

I'm quite interested in the following algorithmic problem, on which I can't find any information. Phrased as a decision problem: Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ ...
4
votes
0answers
107 views

efficiently computing a sum of products of polynomials

Let $F$ be a prime finite field. Let $d$ be a power of two dividing $p-1$. Suppose I have $d$ pairs of univariate polynomials $f_i,g_i$ over $F$ for $i=1,\ldots,d$. All have degree less than $d$. I ...
1
vote
0answers
35 views

Complexity Lower Bounds for 3D Sparse Gaussian Elimination

I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ...
2
votes
0answers
30 views

Complexity of best folding of a 2D set (or how to optimize a sandwich)

Motivation: I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
43
votes
7answers
16k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
1
vote
1answer
113 views

Linear regression as a hylomorphism

A hylomorphism consists of an anamorphism followed by a catamorphism. Is it possible to express linear regression as a hylomorphism?
1
vote
1answer
151 views

Face-splitting product of two Vandermonde matrices: When is is invertible?

Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that ...
7
votes
0answers
147 views

Reference for computing the rank of a matrix in polynomial time

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
4
votes
0answers
82 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
3
votes
1answer
209 views

When is it hard to invert a sparse matrix?

Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication? In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, ...
1
vote
1answer
189 views

What is the complexity of this submatrix selection problem?

We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks. We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
85
votes
2answers
29k views

What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
1
vote
0answers
52 views

Computational complexity in linear solvers

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain ...
6
votes
0answers
163 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
-3
votes
1answer
64 views

Finding a non-negative solution to an integer system of linear equations

Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
15
votes
2answers
5k views

What is the fastest algorithm to compute rank of a rectangular matrix?

Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns? I am aware it can be solved through linear matroid intersection, which ...
8
votes
1answer
199 views

The complexity of the permanent of low rank matrices

I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
7
votes
0answers
151 views

Algebraic methods for testing planarity

Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
19
votes
2answers
939 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 ...
4
votes
0answers
644 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 ...
4
votes
2answers
195 views

What are some good resources for strengthening my theoretical foundation for machine learning?

I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
41
votes
3answers
5k views

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here. I have asked some people who are ...
2
votes
1answer
164 views

Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

I have a set of $n$ convex polytopes of the form $$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$ where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
1
vote
0answers
51 views

Underlying codes in Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d= min\lbrace k \text{ such that there are $k$ linearly ...
8
votes
3answers
650 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
5
votes
0answers
60 views

Hardness result or reference for optimal Gaussian elimination process

I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome. Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\mathbb ...
5
votes
0answers
213 views

Is there a fast algorithm for inverting a sparse matrix?

I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
0
votes
0answers
32 views

Does optimal fitting flat must pass through the mean of the point set?

I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line. Project clustering is a natural generalization of k-...
1
vote
0answers
83 views

Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity

In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf . I don't state the full lemma ...
12
votes
1answer
694 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 ...
10
votes
0answers
150 views

Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed. This means that Banach spaces and short linear maps ...
2
votes
1answer
137 views

Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting $$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
30
votes
2answers
844 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity ...
3
votes
2answers
615 views

Matrix multiplication algorithms for research

I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for ...
3
votes
0answers
178 views

Complexity of eigenvalue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
6
votes
1answer
418 views

What are the consequences of solving XOR 3-SAT in Logspace?

XOR Formulas Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
6
votes
2answers
719 views

Has anyone mixed linear algebra with formal language theory in this way?

Let $G$ be the grammar: $$ S \rightarrow aAb \\ A \rightarrow aA + a + \epsilon $$ where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. ...
6
votes
0answers
305 views

Spectral Graph Theory and Matroid Theory

I have just started grad school this year and I have been into Spectral Graph Theory for some time now. Recently I got introduced to Matroid Theory and although I know the field has been around for ...
4
votes
1answer
793 views

A matrix rank problem over finite fields: Is that a known problem?

The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated. Let $A \odot B$ denote elementwise multiplication of ...
2
votes
0answers
64 views

Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?

Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
8
votes
1answer
5k 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
2 3 4 5