Questions tagged [linear-algebra]
The linear-algebra tag has no usage guidance.
262
questions
1
vote
0
answers
29
views
For a matrix in a row-echelon form, what's a good algorithm to find the free variables?
Suppose I have a reduced row echelon form of a matrix for linear equations. The pivots from the corresponding Gaussian elimination are available. For example, in
$$
\begin{pmatrix}
1 & 0 & 0 \\...
- 111
2
votes
1
answer
38
views
Straight forward algorithm for obtaining a sub matrix
Ok so I just started writing a linear algebra toolbox in C++ for some other projects I have / plan on starting in the future.
So I define a matrix as the fundamental building block and vectors, ...
- 21
1
vote
0
answers
21
views
Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors
I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ...
- 111
1
vote
0
answers
15
views
Effect of using signed vectors for LSH Random Projection (Simhash)
Simhash is an text similarity algorithm proposed by Moses Charikar in his paper "Similarity Estimation Techniques from Rounding Algorithms". However, in his original paper, he proposed to ...
- 111
0
votes
0
answers
27
views
Kronecker Decomposition Algorithm
I am looking for an algorithm that decomposes a $2^n$ square matrix into a Kronecker product $\otimes$ of $n$ number of $2 \times 2$ matrices.
Does anyone know if there is an implementation out there ...
- 101
0
votes
1
answer
29
views
Fit data to a lookup table
I have been looking for methods to fit 1-D data to a lookup table. In other words, there's no known function that is used as a model.
For example in the plots below, the measured data (blue) is fit to ...
- 1
2
votes
1
answer
31
views
Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank
Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal.
I am wondering if anyone have seen ...
- 225
1
vote
1
answer
23
views
Algorithm for solving linear equations if interested only in the first component
If I want to solve $\mathbf A \mathbf x = \mathbf b$, but I am only interested in the value of $x_1$, what algorithm should I use, and will it always be strictly more efficient than solving for all of ...
- 13
5
votes
1
answer
63
views
Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points
Given a set of points $S$ which is a subset of a vector space $V$ I want to want the smallest subspace of $A$ of $V$ such that $|A \cap S| \geq k $.
I suspect some variant of this problem would have ...
- 225
3
votes
1
answer
86
views
How does numpy.linalg.inv calculate the inverse of a matrix?
What is the algorithm behind this routine and is there documentation available for it?
- 31
0
votes
1
answer
36
views
Strange notation in the article about sparse self-attention
While reading an article devoted to the sparse self-attention, I came across a notation that was not very clear:
$$
Attend(X, S) =
\Big(
a(x_i, S_i)
\Big)_{i∈{\{1,...,n}\}}
$$
What means $\Big( \space ...
- 3
3
votes
1
answer
94
views
Mathematical operation for removing duplicate rows in a matrix
I am using the GraphBLAS C API (https://graphblas.org/) which provides an interface for performing mathematical operations on sparse matrices. Given an adjacency matrix $\mathbf{A}: \mathbb{R}^{n \...
- 306
0
votes
1
answer
40
views
Finding solution to Mv=v over $\mathbb{Z}$={0,1} for matrix M given a set linearly independent v
Under mod 2 arithmetic ($\mathbb{Z}$={0,1}), given a set $V$ of $n$x$1$ linearly independent vectors $\{x_1,...,x_n\}$ I'd like to find a $n^2$ binary matrix $M$ such that $Mv=v$ where $v \in V$ and $...
- 404
2
votes
1
answer
79
views
Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)
I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\{\mathbf{0}\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\...
0
votes
0
answers
36
views
Modify this GEPP algorithm to work with matrices
I've been stuck with this problem for a day or so, and I really can't figure it out. I need to modify this pseudocode so that it works when b is not just a vector, but a matrix with same number of ...
0
votes
2
answers
105
views
Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?
Can any SAT problem be converted into one with only affine formulas?
Handbook of Satisfiability p. 672:
Affine formulas. A linear equation over the two-element field is an expression of the form $x_1 ...
- 154
1
vote
0
answers
16
views
Optimal top-k column subset
Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
- 141
0
votes
0
answers
52
views
Getting a V-representation from an H-Representation of a polytope
I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
- 341
0
votes
0
answers
20
views
Are there free/paid DISTRIBUTED solvers for a large system pf linear equations?
I've been doings some research into distributed solutions for a large system of linear equations (reading papers such as Wang et al.'s "Solving a system of linear equations: From centralized to ...
- 1
0
votes
1
answer
59
views
Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities?
I recently discovered linear programming and it seemed perfect for a CS problem I wanted to solve a few months ago. This task involved solving a large quantity of inequalities at once.
For example, ...
4
votes
2
answers
117
views
Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$
Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(...
- 141
1
vote
0
answers
21
views
Algorithm for checking whether a set of hyperplanes covers $\mathbb{Z}_r^n$
In what follows, $r \in \mathbb{N}$ is not necessarily prime. $\mathbb{Z}_r$ is shorthand for $\mathbb{Z}/r\mathbb{Z}$.
Given a set of $h$ hyperplanes $A \vec x = b \mod r$, we can check whether the ...
- 378
3
votes
1
answer
89
views
A version of Bareiss algorithm or similar for symmetric matrices
A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
- 96
1
vote
0
answers
43
views
Algorithm for the inversion of a striped matrix with tridiagonal stripes
I'd like to compute the inverse of a matrix of size $S^2N \times S^2N$ over complex numbers that is composed of tri-diagonal $S\times S$ size blocks of tri-diagonal $S\times S$ block matrices. This ...
- 11
5
votes
1
answer
69
views
Find orthogonal (integer) vectors in set
I have very large sets $A,B$ of 4-tuples of integers, and I would like to find $(x_1,y_1,z_1,w_1)\in A,(x_2,y_2,z_2,w_2)\in B$ such that
$$x_1x_2 + y_1y_2 + z_1z_2 + w_1w_2 = 0.$$
Of course the naive $...
- 281
2
votes
0
answers
68
views
Permuting matrix entries to lower rank
Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
- 43
0
votes
3
answers
65
views
Linear algebra matrix coding to solve specific formula
I have a formula which cannot be expressed in terms of y.
...
- 103
1
vote
2
answers
605
views
Can dot producting the result of vector-matrix multiplication speed up the runtime?
Suppose we have a matrix $A$ of dimension $n \times n$ and two vectors $\vec{u}$ and $\vec{v}$ of dimension $n$.
Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(...
- 187
1
vote
1
answer
42
views
Efficiently finding/ sampling from all solutions to a constrained linear problem
Start with $N>3$ vectors $\vec{v}_I$ in $\mathbb{R}^3_+$, any $3$ of which are linearly independent. $I$ here ranges from $0$ to $N-1$.
Let $v_{\left[abc\right]}$ be a matrix in $\mathbb{R}^{3 \...
- 113
0
votes
0
answers
56
views
Complexity of calculating Takagi's factorization of $n \times n$ matrix
As described here the Takagi factorization of a square symmetric complex matrix $A=VDV^T$ where D is a real nonnegative diagonal matrix, and V is unitary. I'm wondering what the complexity of ...
- 53
1
vote
0
answers
24
views
Element in linear subspace with maximum number of zeros
Given a real matrix $M \in \mathbb{R}^{n \times m}$ and a vector $v \in \mathbb{R}^{n}$ I would like to find an element $x \in \mathbb{R}^m$ such that $v - Mx$ has maximum number of zeros.
If the ...
- 111
0
votes
1
answer
10
views
Checking for equality before calculating product of a matrix with inverse of another matrix
I have an operation that is performed many times and is thus performance sensitive where I need to calculate product of a matrix and inverse of a matrix as below. Both matrices are 4x4 and consist of ...
- 177
1
vote
1
answer
80
views
Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector?
Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I ...
- 13
2
votes
0
answers
42
views
Solving Small even set problem (SES) using Shortest lattice vector problem (SVP)
Suppose that you are given an algorithm A that finds the optimal solution to the shortest lattice vector problem (SVP) in time $t(n)$
I am trying to solve the Small even set problem (SES) using it:
...
- 21
1
vote
0
answers
69
views
Estimating column sums of $A_1,\ A_1 A_2,\ A_1A_2A_3,\ \ldots$
Given $n\times n$ dense real valued matrices $A_1,\ldots, A_L$ let $P_i=A_1\ldots A_i$
For each $P_i$ I'm interested in obtaining the sum of all rows, and the sum of all columns.
Naive approach:
...
- 201
0
votes
0
answers
98
views
Given a 2D Array (of 0's and 1's), find the minimum number of rows required so that maximum columns have their sum greater than a threshold
I have a 2D array of some rows and columns which are having only 0's and 1's. I would want to know if there is a way to optimize the number of rows so that maximum number of columns have their column ...
1
vote
0
answers
38
views
Fourier Dimension of Boolean functions
I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
- 123
1
vote
2
answers
265
views
Clarification regarding linear boolean functions!
I am a little confused when it comes to linear boolean functions.
According to this post:
What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
- 13
1
vote
1
answer
326
views
Complexity of finding $d$ largest eigenvectors of a symmetric matrix
I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
- 123
0
votes
1
answer
44
views
Getting a "sub-polytope" of a concave d-dimensional polytope, given some one dimensional inequality
The question will be hard to understand without an example, so let's given an example first:
Let's say I have a 2 dimensional concave polytope, defined by a circular sequence of its vertices:
$(0,0),
(...
- 13
1
vote
0
answers
211
views
Is there an alternative method to using Gaussian elimination in order to solve 3-XORSAT
I have a large system of $3$-$XORSAT$ constraints (i.e. up to $3$ variables per constraint) and this can be represented in matrix form as a linear algebra problem $Ax=b$ $mod$ $2$. Solvability (i.e. ...
- 11
1
vote
1
answer
43
views
(Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory [closed]
The Weight Distribution / Subspace Weights Problem in coding theory is defined as this:
Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$
Question: Is there a set of $k$ columns of $...
- 11
0
votes
1
answer
118
views
Finding a $d$-dimensional hyperplane containing $n$ given points
I'm currently trying to find the equation of the $d$-dimensional hyperplane which includes $n$ given points, where $n \ge d$.
Theoretically, it isn't hard - the $d$-dimensional hyperplane is ...
- 13
1
vote
0
answers
24
views
Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?
This problems comes from AI, and it looks something like this:
I am supposed to multiply two floating-point matrices A * B. A ...
- 11
0
votes
0
answers
21
views
Is one set of vectors constructed by another set of vectors?
Let there be given set of vectors $V = \{v_1, v_2, ..., v_n\}$ and set of vectors $S = \{s_1, s_2, ..., s_k\}$ where $n > k$. The set of vectors $V$ can be constructed by $S$ if the vectors in $V$ ...
- 1
0
votes
0
answers
46
views
Which of these algorithms will involve the least amount of math?
I'm taking an algorithms class for my computer science degree, and one of the requirements is to research and present 3 different algorithms. The only problem: linear algebra wasn't a prerequisite to ...
0
votes
0
answers
45
views
Finding a set of 9 integers that minimize an error function
I have an algorithm that takes a 3d triangle PMN(which is constructed from running a function that converts per-vertex UV coordinates to a PMN triangle) and P' which is a randomly chosen 3D point that ...
- 101
5
votes
0
answers
103
views
Optimization problem with discrete and continuous components
Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between ...
- 265
0
votes
0
answers
35
views
Kalman Filter - Dynamic System
Given the two equations below
$$ \begin{aligned} 300x + 400y &= 700 \\ 100x + 133y &= 233 \end{aligned}$$
how can one find a solution for those equations using Kalman filter (and suppose the ...
- 97
3
votes
0
answers
44
views
Bound on the number of signed sums of a non-zero vector that can all equal zero
Let $u$ be a real vector of $m$ entries, and $A$ be a $\pm 1$ matrix of dimension $N\times m$, and real rank $\operatorname{rank}(A) = r$.
What are some conditions on $A$ (e.g. in terms of its rank $r$...
- 991