2022 Developer Survey is open! Take survey.

Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

Filter by
Sorted by
Tagged with
3 votes
1 answer
153 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 $\...
user avatar
  • 191
8 votes
0 answers
108 views

improved analysis of spectral gap of zigzag product?

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction: Moreover, the variational ...
user avatar
  • 81
6 votes
2 answers
141 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 ...
user avatar
  • 226
3 votes
1 answer
161 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)...
user avatar
  • 31
1 vote
0 answers
31 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 ...
user avatar
1 vote
0 answers
65 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 $\...
user avatar
  • 31
1 vote
0 answers
104 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 ...
user avatar
3 votes
0 answers
62 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?
user avatar
2 votes
1 answer
116 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), ...
user avatar
  • 1,398
3 votes
1 answer
60 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, ...
user avatar
  • 133
0 votes
0 answers
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$ ...
user avatar
4 votes
0 answers
109 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 ...
user avatar
  • 217
1 vote
0 answers
51 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 ...
user avatar
3 votes
1 answer
229 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}\...
user avatar
2 votes
0 answers
31 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 ...
user avatar
  • 5,246
1 vote
1 answer
117 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?
user avatar
7 votes
0 answers
158 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 ...
user avatar
1 vote
1 answer
174 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 ...
user avatar
  • 1,095
4 votes
0 answers
86 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 ...
user avatar
  • 454
5 votes
1 answer
259 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, ...
user avatar
1 vote
1 answer
230 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 ...
user avatar
  • 12.5k
1 vote
0 answers
62 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 ...
user avatar
-3 votes
1 answer
85 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 $...
user avatar
  • 215
9 votes
1 answer
223 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 ...
user avatar
  • 93
7 votes
0 answers
157 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 ...
user avatar
  • 215
4 votes
2 answers
208 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 ...
user avatar
41 votes
3 answers
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 ...
user avatar
  • 511
2 votes
1 answer
167 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 $$(\...
user avatar
1 vote
0 answers
52 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 ...
user avatar
  • 387
5 votes
0 answers
62 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 ...
user avatar
5 votes
0 answers
216 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 ...
user avatar
  • 235
0 votes
0 answers
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-...
user avatar
1 vote
0 answers
93 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 ...
user avatar
  • 11
10 votes
0 answers
157 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 ...
user avatar
8 votes
3 answers
734 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$ ...
user avatar
2 votes
1 answer
142 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{ ...
user avatar
  • 185
6 votes
1 answer
493 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 $\...
user avatar
2 votes
0 answers
66 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 ...
user avatar
2 votes
0 answers
92 views

Why is triangle inequality needed for indexing?

Maybe this is a silly question but I actually can't fulfill that by myself. I'm reading some papers about similarity metrics and I always find that for a distance function $d$ the triangle inequality ...
user avatar
11 votes
1 answer
248 views

Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector. Conjecture: If $t$ can be written as ...
user avatar
  • 5,225
11 votes
1 answer
351 views

Is there a P-complete problem on diophantine equations?

In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
user avatar
3 votes
0 answers
66 views

Minimizing a sum of thresholded quadratics

Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors, and $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of ...
user avatar
  • 31
6 votes
1 answer
250 views

Algebraic account of Gaussian elimination?

For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting question about the interpretation of double-negation-...
user avatar
6 votes
0 answers
171 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 $$\...
user avatar
  • 271
0 votes
1 answer
32 views

Decomposing outer product or general rank factorization over $\Bbb F_q$

Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$...
user avatar
  • 12.5k
-1 votes
1 answer
106 views

given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?

given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $...
user avatar
2 votes
1 answer
90 views

Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636 So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
user avatar
  • 1,443
2 votes
0 answers
65 views

A random ensemble of sparse boundary operators

The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
user avatar
  • 1,214
3 votes
1 answer
102 views

About the sign-rank of the Minsky-Pappert function

Apologies this might be a very trivial thing I am getting confused by! Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ...
user avatar
  • 1,443
4 votes
0 answers
84 views

About Boolean functions with a high sign-rank

Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
user avatar
  • 1,443

1
2 3 4 5