Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
230 questions
1
vote
0
answers
58
views
Large vector families with certain spanning properties on percolation
I'm interested in large families of vectors, which include many large linearly-independent sets, with the property that percolation results in any individual vector in the family not being spanned ...
- 593
0
votes
1
answer
156
views
Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2
Consider a set of natural numbers $S \in \mathbb{N}^n$ for some $n \in \mathbb{N}$. Assume that each number $s_i = S^T\cdot e_i$ meets $s_i \leq 2^m$ i.e. is written on at most $m$ number of digits, ...
- 141
11
votes
1
answer
390
views
Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"
I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i).
The proof starts by saying
Clearly, $...
- 113
3
votes
0
answers
47
views
Affine point matching in general dimensions
Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
- 151
3
votes
0
answers
59
views
Name for the dimension of subspace of support of boolean function?
The support of a boolean function is defined as the set of $x$ such that $f(x) = 1$. I want to quantify the dimension of the support of the function (i.e. how large the subspace is that is made up of ...
- 131
1
vote
0
answers
55
views
Find linear combination with small support
Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...
- 191
-3
votes
1
answer
112
views
Algebra in complexity theory
Recently an idea came to my mind. Suppose $V$ is vector space and $\dim V = n$. Then, since $V \simeq \mathbb{R}^n$, any conjunction of $n$ boolean formulas $\phi_1, \ldots, \phi_n$ about vectors from ...
- 1
4
votes
0
answers
58
views
Approximate Matrix Multiplication with approximation guarantees that ignore large elements?
Approximate matrix multiplication is a technique to replace a matrix product $A^t B$ with a smaller product $(\Pi A)^t(\Pi B)$.
Intuitively, if $\Pi$ is chosen from a suitable distribution that has
...
- 978
5
votes
1
answer
255
views
On the plausability of quantum RAM
I'm fairly new to quantum computation and quantum complexity theory, but I came across some articles that suggest that quantum RAM (QRAM) is not very realistic assumption. For example some works show ...
- 161
1
vote
0
answers
69
views
Circuit depth of linear algebra operations
I was checking the following paper [1] about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not ...
- 161
0
votes
1
answer
206
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
166
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
1
vote
1
answer
70
views
Impact HHL caveat relaxation on quantum advantage
We know that there are four caveats for the exponential speedup proven for the HHL algorithm. Could anyone answer how that exponential speedup evolves as we relax the caveats?
For example, the ...
- 661
3
votes
2
answers
896
views
Johnson-Lindenstrauss and the largest eigenvalue of a matrix
Johnson-Lindenstrauss (JL) lemma shows that for any vector $u$ in $\mathbb{R}^d$, the vector $\frac{1}{\sqrt{k}}Ru$ satisfies $(1-\epsilon)\|u\|\leq \frac{1}{k}\|Ru\|^2\leq (1+\epsilon)\|u\|$ with ...
- 253
0
votes
1
answer
78
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
4
votes
0
answers
160
views
Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$
$\newcommand{\F}{\mathbb{F}}\newcommand{\R}{\mathbb{R}}$
Question is in the title basically: does there exist a Boolean matrix $M$ where $\operatorname{rank}_{\F_2}(M)=r$ but $\operatorname{rank}_{\R}(...
- 59
2
votes
2
answers
169
views
Are there publicly available fast Laplacian solvers?
In a much celebrated result, we know that there is a $ O(m\log \frac{1}{\epsilon}) $ time algorithm for solving laplacian systems of the form $Lx=b$ where $L$ is a laplacian of a graph $G$ with $m$ ...
- 1,163
3
votes
1
answer
116
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 682
27
votes
1
answer
541
views
How many multiplications are needed to compute the determinant of a 3×3 matrix?
In a comment on this question in 2016, Jeffrey Shallit remarked:
I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute ...
- 761
3
votes
1
answer
1k
views
Complexity of matrix diagonalization
I'm probably missing a trivial answer, but somehow I can't find it.
Given symmetric matrix $A \in \mathbb R^{n \times n}$, what's the complexity of diagonalizing the matrix, i.e. finding diagonal $\...
- 256
6
votes
2
answers
321
views
Reference request for linear algebra over GF(2)
I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
- 300
3
votes
1
answer
173
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)...
- 31
1
vote
0
answers
34
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 ...
- 111
1
vote
0
answers
76
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 $\...
- 31
1
vote
0
answers
116
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 ...
- 89
4
votes
0
answers
74
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
1
answer
120
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), ...
- 1,901
3
votes
1
answer
73
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, ...
- 133
0
votes
0
answers
25
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
0
answers
116
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 ...
- 289
1
vote
0
answers
68
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 ...
- 111
3
votes
1
answer
235
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}\...
- 265
2
votes
0
answers
34
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 ...
- 5,636
1
vote
1
answer
125
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?
- 785
7
votes
0
answers
303
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 ...
- 171
1
vote
1
answer
231
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 ...
- 1,481
4
votes
0
answers
92
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 ...
- 696
5
votes
1
answer
391
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, ...
- 4,731
1
vote
1
answer
346
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 ...
- 13.3k
1
vote
0
answers
100
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 ...
Inershya
-3
votes
1
answer
145
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 $...
- 215
10
votes
1
answer
282
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 ...
- 103
7
votes
0
answers
185
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 ...
- 215
5
votes
2
answers
309
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 ...
- 61
43
votes
3
answers
6k
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 ...
- 531
2
votes
1
answer
174
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
0
answers
55
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 ...
- 387
5
votes
0
answers
82
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 ...
- 101
5
votes
0
answers
222
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 ...
- 235
0
votes
0
answers
35
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-...
- 265