Questions tagged [linear-algebra]
The linear-algebra tag has no usage guidance.
250
questions
0
votes
2
answers
50
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 ...
- 146
1
vote
0
answers
13
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
18
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}^...
- 291
0
votes
0
answers
19
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
0
answers
15
views
Algorithm for computing the vertices of a polytope defined as the intersection of half spaces
There's a very similarly sounding question with an answer already, but my setup is very, very different.
You are given $k$ half spaces in dimension $d$, defined by a point and a direction. You want to ...
- 291
0
votes
1
answer
36
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
81
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
2
votes
1
answer
67
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 ...
- 71
0
votes
0
answers
6
views
Does T5 or another embedding embed every possible length tokenization?
I’m curious about an embedding technique where every possible “tokenization” of a text gets an embedding - not just individuals words, but every single 2-gram, 3-gram, and n-gram.
Does this exist?
Or ...
- 23
1
vote
0
answers
30
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
59
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
60
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
54
views
Linear algebra matrix coding to solve specific formula
I have a formula which cannot be expressed in terms of y.
...
- 103
0
votes
0
answers
44
views
The solution of a nonlinear equation and eigenvalues
I have a non-zero vector $x = [x_1,\cdots,x_N]$, $0 \le x_i \ll 1$ and a symmetric matrix $M$ with eigenvalues $\Lambda_1 > \Lambda_2 \ge \dots \ge \Lambda_N$ satifying $$ x_i = \frac{\lambda\sum_{...
- 101
1
vote
2
answers
360
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(...
- 177
1
vote
1
answer
34
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
46
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
18
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
52
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
38
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
68
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
60
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
25
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
212
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
104
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
35
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
144
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
26
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
38
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
21
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
45
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
100
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
33
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
0
votes
1
answer
55
views
can similarity transformation be linear transformation?
Learning Computer Graphics -
Can similarity transformation be linear transformation?
Similarity T is a rigid transformation (translation and rotations) with uniform scaling.
so I guess a similarity ...
2
votes
1
answer
48
views
What is this linear optimization problem?
Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$.
Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
- 385
0
votes
0
answers
25
views
How to eliminate « a priori » all vectors in a list of vectors whose scalar product with a given vector is zero without calculating the product
How to eliminate « a priori » all vectors in a list of vectors, whose scalar product with a given vector is zero, without actually calculating the product ?
One solution would be to store the ...
- 165
0
votes
0
answers
43
views
Recommendations on where to learn and practice linear programming?
[CLOSED] Thanks!
I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts.
So do you have any recommendations of materials to learn or practice Linear ...
0
votes
1
answer
25
views
Lower bound on number of zero columns in matrix
I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
- 41
2
votes
0
answers
58
views
Best grid/lines to map a group of points
The data I have is a group of points with their position (x,y) known:
It is known that all these red dots are situated exactly on the lines which form a grid system like following:
My object is to ...
- 121
10
votes
1
answer
1k
views
Why is the probability of a false positive not 0 for Freivald's Algorithm?
Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $n \times n$-matrices $A$ and $B$ yields a given matrix $C$ (i.e. $AB = C$). The way this task is ...
- 103
3
votes
2
answers
818
views
How to setup the Bellman Equation as a linear system of equation
I was watching a video on Reinforcement Learning by Andrew Ng, and at about minute 23 of the video he mentions that we can represent the Bellman equation as a linear system of equations. I am talking ...
- 151
1
vote
2
answers
234
views
Fast computing of a matrix power for large integer values in C++
I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix.
My objective is to compute the power of the squared matrix ...
- 113
1
vote
0
answers
31
views
Least probability of collisions using rgb as a hash map
I need to rewrite a short utility library, to get it working with the Brave browser (My actual question isn't about brave per se.)
canvas-color-tracker - example of it being used and src/index.js is ...
- 11
2
votes
1
answer
79
views
Why is CNOT the only non-trivial reversible gate for two input bits?
The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function:
$$
00 \to 00 \\ 01 \to 01 \\ 10 \to ...
- 21
0
votes
0
answers
39
views
Choosing unsupervised learning algorithm for analyzing the spectrum of a linear operator
I am a theoretical physicist, and new to CS.stackexchange, and have a little knowledge of CS, and in Machine Learning (only some general stuff). In physics we often analyze the spectrum of linear ...
- 101