Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
0answers
124 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
1
vote
0answers
69 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 ...
0
votes
1answer
53 views

Compute unknown matrices that minimize a sum

This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|...
2
votes
1answer
15 views

Strassen's algorithm on unit vectors?

I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum. ...
3
votes
1answer
111 views

Interpreting camera matrix

I'm having some trouble interpreting the camera matrix $K = \begin{bmatrix} f_x & s & x_0 \\ 0 & f_y & y_0 \\ 0 & 0 & 1 \end{bmatrix}$ after it multiplies some 3D vector. ...
1
vote
1answer
487 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 ...
2
votes
1answer
66 views

Is it possible to transfer a point from one camera to another, given n corresponding points?

I have 2 images of a scene taken at one moment by two identical cameras (similar cameras intrinsic parameters) by to arbitrary locations and at two arbitrary orientations (different cameras poses). On ...
3
votes
1answer
127 views

Eigenvalue computation for large graph

Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it ...
4
votes
2answers
67 views

Among $k$ unit vectors, find odd set with sum length less than 1

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
0
votes
1answer
619 views

Cache efficient matrix multiplication

Consider these matrices: $A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$ $B=\begin{bmatrix}-1 & -2\\-3 & -4\end{bmatrix}$ Using standard algorithm: $C=\begin{bmatrix}1*-1+2*-3 & 1*...
5
votes
2answers
167 views

Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero

Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero? It is ...
0
votes
1answer
290 views

LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
2
votes
0answers
70 views

Complexity of a submatrix rank problem

Given a matrix $M \in \mathbb{R}^{n \times m}$ and a set $S \subset \{1, \ldots, n\}$, let $M_{S, {\rm row}}$ be the matrix obtained by picking the rows of $M$ from the set $S$. Similarly, given $S' \...
1
vote
0answers
25 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 ...
3
votes
2answers
512 views

Is the Tomasi-Kanade factorization still commonly used as a modern computer vision technique?

My understanding is that, in very rough terms, the Tomasi-Kanade algorithm published in 1992 describes a way to reconstruct the 3D structure of an object from multiple images of that object, given ...
0
votes
1answer
313 views

maximizing inner product of vectors in an ellipsoid and a given vector

I have been wrestling with this for quite a long time but couldn't convince myself that the following is true: What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid....
2
votes
0answers
82 views

Vandermonde matrix and its binary representation

Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
0
votes
0answers
153 views

Why solutions for Normal form Ordinary least squares and Linear Regression are different

I am trying to apply Linear Regression method for a dataset of 9 sample with around 50 features using python. I have tried different methodology for Linear Regression i.e Closed form OLS(Ordinary ...
1
vote
0answers
41 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
32 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
27 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
46 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
73 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
147 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
43 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
5k 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
902 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
79 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
62 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
468 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 $...
3
votes
1answer
828 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
100 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
162 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
800 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
32 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
253 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
1k 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
88 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
207 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
226 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
165 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
210 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 ...
13
votes
2answers
675 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
104 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
729 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
237 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
637 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
315 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
379 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 ...