Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
33 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
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
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 ...
2
votes
0answers
45 views

How many iterations of Lanczos bidiagonalization are required in order to obtain the first k singular values/vectors of a matrix?

I am trying to implement a fast SVD algorithm for obtaining the first $k$ singular values/vectors of an $M\times N$ matrix ($k < \min(M,N)$) using the following 2-step process: 1) bidiagonalize ...
1
vote
1answer
55 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 ...
3
votes
1answer
131 views

Conditions for Linear Diophantine Equations to always have a solution

Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution. Over $\mathbb N$, is there any such ...
2
votes
0answers
40 views

mx2m modulo-3 matrix solution

Is there an efficient algorithm for the following problem? Given: a $m$-vector $b \in \{0,1,2\}^m$, and a $m \times 2m$ matrix $A$, with the promise that for every $b' \in \{0,1,2\}^m$, there exists $...
8
votes
3answers
3k views

Fastest way to solve a system of linear equations

I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is ...
8
votes
2answers
717 views

Could a quantum computer perform linear algebra faster than a classical computer?

Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has ...
2
votes
0answers
64 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}^...
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
244 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
662 views

Absorbing Markov Chains: An efficient algorithmic approach

Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows: Given the ...
3
votes
2answers
98 views

Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
0
votes
1answer
103 views

Using random projections for locally sensitive hashing

I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents. The proof is such that based on cosine similarity to the vector. In other ...
3
votes
1answer
551 views

Finding the bandwidth of a band matrix

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the ...
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 ...
3
votes
1answer
212 views

Count number of linearly independent subsets of columns of a binary matrix

I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly ...
4
votes
2answers
789 views

Time complexity of matrix multiplication in Big-Align

I am reading the following paper: Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013). I'd like to ...
0
votes
1answer
77 views

Projecting points on a Pareto-front onto a (hyper)plane?

I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb. Basically, ...
1
vote
0answers
188 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)$. ...
2
votes
0answers
206 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
127 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 ...
5
votes
0answers
144 views

How to treat numerical errors in determinants of singular matrices when using LU decomposition

I want to calculate the determinant of a matrix. Currently I'm using LU decomposition. To check my algorithm I wrote a unit test with random matrices. In one part I set one row to be equal to ...
11
votes
2answers
555 views

Matrix chain multiplication and exponentiation

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}...
2
votes
1answer
74 views

Efficient algorithm to check if a vector exists in the span of a subset of vectors

I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if ...
3
votes
1answer
725 views

Suitable choice for moderate-size square matrix multiplication?

The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, ...
2
votes
1answer
169 views

How to find subset of vectors whose sum has certain characteristics

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$: $$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &...
0
votes
1answer
585 views

Running time of sparse matrix multiplication

Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
4
votes
1answer
251 views

Minimize the maximum Hamming weight of basis vectors spanning a binary subspace

In the course of my research, I stumbled upon a problem which can be recast as the following decision problem: First some notation: Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^...
1
vote
1answer
266 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 ...
3
votes
1answer
234 views

Positive Definiteness Constraint

I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite. How should I do it? The library I am working with can cope with linear/ quadratic ...
3
votes
1answer
184 views

Derandomization of an approximation algorithm for solving a linear system

I was given a HW assignment that asks me the following: Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment ...
3
votes
0answers
52 views

Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
2
votes
1answer
306 views

Can the unbounded knapsack problem be described as a matrix exponentiation?

It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution. ...
2
votes
1answer
697 views

Locality-sensitive hashing random projection

I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that ...
4
votes
1answer
738 views

Closed form solution for optimization problem

Consider the problem of finding the real-valued matrix $C$ so that $$\|S-AC\|_F^2\qquad(1)$$ is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has ...
2
votes
1answer
38 views

Proving complexity of computing product of matrices

If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
1
vote
1answer
747 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 ...
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 ...
-1
votes
1answer
62 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
2
votes
1answer
227 views

Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
4
votes
0answers
67 views

Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and ...
3
votes
1answer
172 views

How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
5
votes
1answer
692 views

Computing Von Neumann Entropy Efficiently

The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
4
votes
0answers
152 views

Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone generated ...
7
votes
1answer
764 views

It is possible to implement a *greater than* function using only addition, substractions and multiplications?

All values are from a finite field $Z_t$. I want to write a function greater than like this $GT(x,y) = \begin{cases} 1, & \text{if } x > y, \\ 0, & \text{otherwise}. \end{cases}$ ...
4
votes
1answer
209 views

Solving systems of linear equations over semirings

So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
0
votes
1answer
38 views

Using Taylor series in 1D Grayscale Image

Could someone point me in the direction of how to solve this? I = [I1, . . . , In] is a 1D grayscale image and D = [D1, . . . , Dn] represents the second derivative of I. I am given the four pixel ...
3
votes
1answer
76 views

Rank of random binary matrix subset

I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's ...