The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
75 views

Optimal vector decomposition

I have a vector $v \in \mathbb{N}^k$ and a set of vectors $R \subset \mathbb{N}^k$, with $k \ll \left\vert R \right\vert $. I would like to find a way to obtain all the possible bases of $\mathbb{N}^...
2
votes
0answers
217 views

Geometric interpretations of midpoint algorithm, homogeneous linear least squares and nonlinear least squares method in 3D reconstruction?

In "Multiple View Geometry in Computer Vision" Chapter 12. Structure Computation, page 310-313, triangulation is used for point 3D reconstruction. There are three methods mentioned: Midpoint method ...
2
votes
0answers
138 views

Why is my Forrest-Tomlin update worse than recomputing LU?

I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few ...
2
votes
0answers
148 views

Computing $\mathrm{tr}(X^{-1}Y)$ efficiently

I know that one can compute the expression $X^{-1}\mathbf{v}$ quickly with conjugate gradient method. Is there a similar approach for computing $\mathrm{tr}(X^{-1}Y)$? Similarly interesting to me are ...
2
votes
0answers
151 views

Maximum feasible subsystem problem (MaxFS) in 2 variables

Topic: The maximum feasible subsystem problem, which is generally NP-hard [1]. Question: Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
2
votes
1answer
441 views

Implementing the Schur decomposition of a matrix

I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?
1
vote
1answer
295 views

Inputting a superposition into a cNOT gate

I am unsure how to calculate what happens when you put a superposition as the control qubit into a cNOT gate or what happens when you put a superposition as the target qubit into a cNOT gate. I know ...
1
vote
1answer
88 views

What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is ...
1
vote
1answer
190 views

Calculating eigenvalue gap of a torus graph

Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for ...
1
vote
1answer
371 views

Significance of parameters in Tiny Mersenne Twister algorithm

I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ...
1
vote
2answers
104 views

Finding the required value of an algebric expression

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
1
vote
1answer
59 views

What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows: Suppose that the last slack form of the ...
1
vote
2answers
49 views

Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

Is there is an efficient algorithm to solve the following optimization: $\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$ for given $\mathbf{b_i}, \mathbf{A_i}\ \forall ...
1
vote
1answer
60 views

Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants']

This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution It was established in the above's answer that obtaining or testing for the ...
1
vote
1answer
61 views

small size and small depth circuit for set intersections

Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$. Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then ...
1
vote
1answer
31 views

Finding dimensions of a point cloud - floating point issues

I have $N$ data points of some dimension $D$. I want to know the dimension of the shape that those data points represent - for instance they might be a 2 dimensional triangle, even though they are in ...
1
vote
1answer
74 views

Properties of coset

Let $C$ be a linear code with minimum distance $2k$. I want to show that there is a coset of $C$ that contains at least two vectors of weight $k$. Firstly, it holds that the minimum distance of the ...
1
vote
1answer
37 views

Minimise simultaneous equation remainder

I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = [1,4,5,6,3,1,4,5,6,7,...7] and I have a set of ...
1
vote
1answer
310 views

Partially diagonalizing a matrix

Suppose I have an $n\times n$ matrix. I would like to keep an $m\times m$ subblock undiagonized, while keeping the rest diagonized. Is there any algorithm for this? More precisely, I mean using ...
1
vote
1answer
27 views

Recover boolean vector from dot products

Question: I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
1
vote
1answer
92 views

Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
1
vote
1answer
38 views

Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$

Given I have a $n$ dimensional $\vec{a}$. All elements of $\vec{a}$ are between 0 and a positive number $K$. $n$ is about 15 to 20. Problem I want to randomly and unbiasedly choose a vector $\vec{b}...
1
vote
1answer
163 views

In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
1
vote
1answer
313 views

Applications of the LU factorization in computer science [closed]

I have been searching for the applications of the LU factorization/decomposition in computer science. From Wikipedia, I have found some of the applications, but these don't seem to be relevant to ...
1
vote
1answer
31 views

What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form? Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations? Technically $O(n^3)$ row ...
1
vote
1answer
289 views

Approximation of a gaussian function

I want to approximate a Gaussian function as shown below $$ e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)e^{\frac{-\|x-c_i\|^2}{2\sigma^2}} \forall x $$ Here c, $\sigma$ and $...
1
vote
1answer
939 views

Complexity of matrix inverse via Gaussian elimination

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
1
vote
1answer
129 views

Scheduling distributed computational graph

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete. The common way to improve simulation performance is to use a suitable distributed linear ...
1
vote
1answer
170 views

Creating a single layer perceptron for the OR problem

I am working on the following problem Find the linear least squares unit weights for the `OR' problem, ie. $v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and $u_1 = 0, u_2 = u_3 = u_4 = ...
1
vote
0answers
18 views

Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
1
vote
0answers
31 views

Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
1
vote
0answers
23 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given $$ a_1 X_1 + \dots + a_n X_n = b $$ where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,...
1
vote
0answers
13 views

Convergence of Conjugate gradient method

I have implemented my own matrix library in Java to solve fluid simulations. So I have also implemented the conjugate gradient method and I got a little bit confused. What I have done to test my CG-...
1
vote
1answer
23 views

Underlying codes for 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 ...
1
vote
0answers
31 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
1
vote
0answers
32 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
1
vote
0answers
72 views

Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
1
vote
1answer
17 views

Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
1
vote
0answers
34 views

Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
1
vote
0answers
25 views

Need help implementing an algorithm to solve roots of a transcendental equation

I'm trying to implement this algorithm but I'm having problems reproducing the exemple that it gives a solution to. The general method that I tried is: Make a grid $\theta \in [0,2\pi)$, with say N=...
1
vote
0answers
61 views

Sparse Matrix inversion without actual inversion

I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix? Thank you ...
1
vote
0answers
25 views

Construct unitary $Q$ such that $span\{q_1,q_2\} = span\{v_1,v_2\}$ where $v_1,v_2 \in \mathbb{R}^n$ are given as input

Assume also that $v_1,v_2$ are linearly independent, and $q_i \in \mathbb{R}^n$ denotes the $i$-th column of $Q$. This is what I've got so far. First obtain unit vectors $w_1,w_2$ which are orthogonal ...
1
vote
0answers
24 views

Want to do 3D reconstruction via simple matching

I have 2 images, called left and right images. I have some matched points $[c_l,r_l]$ and $[c_r,r_r]$ in both of them (these points are in pixel coordinates). For a 3D point in the real world, they ...
1
vote
0answers
35 views

Scalability of factor-solve vs. pseudoinverse + product

I’ve always read advice and warnings about the poor scalability and time spent trying to invert a matrix and why it’s better to solve a system of equations whenever the inverted matrix will be used ...
1
vote
0answers
26 views

Testing whether a set of integers can be written as a combination of module basis elements

Input We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$} Desired Output Return true if there ...
1
vote
0answers
199 views

How to solve linear system with modulus operation?

I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$. ...
1
vote
0answers
76 views

Relation between determinant and matrix multiplication

I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be ...
1
vote
0answers
39 views

2 qubits, correct way CNOT a 3rd qubit with the 1st? [duplicate]

Suppose I have 2 qubits in the state a|00>+b|01>+c|10>+d|11>. And suppose I want to perform some operation between only the 1st qubit and a 3rd qubit - for example a CNOT operation. What would be ...
1
vote
0answers
34 views

Matrix whose eigenvectors are Hermite polynomials [closed]

I first constructed a symmetric matrix as the Laplacian operator, and its eigenvectors are a series of harmonics functions as expected. I programmed it and convinced myself. The matrix looks like: $$ \...