Questions tagged [linear-algebra]

The tag has no usage guidance.

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 ...
1
vote
0answers
29 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\...
0
votes
1answer
18 views

Geometric median of two disjoint sets of points lies on line between their respective medians

I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ...
2
votes
1answer
21 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
2
votes
1answer
42 views

Randomly construct linear combination that is within bounds over two basis

Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that: $0 \le x_{j} \le 1$ $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$ Matrix $A$ is about 10 x 15. I want to ...
2
votes
1answer
26 views

What's the connection between the two “Fast Walsh Transform”?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
0
votes
0answers
52 views

How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
0
votes
0answers
31 views
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 ...
3
votes
1answer
91 views

Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
2
votes
0answers
38 views

Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
6
votes
2answers
148 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
1
vote
1answer
16 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
1answer
50 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
0answers
54 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
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 ...
0
votes
0answers
26 views

Equivalent Algorithm with Sharman Morrison inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
2
votes
0answers
44 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
1
vote
1answer
80 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 ...
3
votes
2answers
239 views

Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
2
votes
1answer
33 views

Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
0
votes
0answers
32 views

Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
1
vote
1answer
62 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. ...
0
votes
1answer
18 views

Avoiding underflow when identifying neighbours of a cell in a grid by using modulo

I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, ...
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
0answers
31 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 ...
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, ...
1
vote
0answers
14 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
1answer
111 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 ...
4
votes
1answer
187 views

Minimize sum of squares of rows in matrix when sum of columns have some constraint

I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that $$ \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2 $$ is minimal, while also for each $j\in J$ satisfying the constraint ...
4
votes
0answers
112 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
21 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=...
5
votes
2answers
324 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
2
votes
2answers
333 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 ...
1
vote
0answers
48 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 ...
11
votes
1answer
4k views

Complexity of finding the pseudoinverse matrix

How many arithmetic operations are required to find a Moore–Penrose pseudoinverse matrix of a arbitrary field? If the matrix is invertible and complex valued, then it's just the inverse. Finding ...
4
votes
1answer
64 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
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 ...
8
votes
1answer
787 views

Inverting a band matrix

I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following: Here, the area under the blue stripes is the non-zero elements; everything else is ...
0
votes
1answer
48 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
12 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. ...
1
vote
1answer
275 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 ...
2
votes
1answer
57 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 ...
1
vote
1answer
237 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 ...
3
votes
1answer
79 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
58 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
377 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
111 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
191 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
56 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' \...