Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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, ...
3
votes
2answers
325 views

Solving/Optimizing a linear system in a finite field (Z/2Z)

I'm trying to solve the following optimization problem. A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y ...
3
votes
1answer
759 views

Why linear transformation can improve classification accuracy when the dimensionality of data is high?

Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset. When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more ...
3
votes
1answer
399 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
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 ...
3
votes
1answer
105 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$ ...
3
votes
1answer
90 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 ...
3
votes
1answer
136 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 ...
3
votes
1answer
199 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 ...
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 ...
3
votes
1answer
2k views

Efficient computation of Kronecker product

Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such: $M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty ...
3
votes
1answer
3k views

Machine Learning: how to correctly calculate gradient descent for simple linear problem

So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on ...
3
votes
1answer
3k views

how to represent Sparse Matrices [closed]

I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices. Could you please suggest me some other way to store/represent sparse ...
3
votes
1answer
737 views

Counting solutions to system of linear equations modulo prime

I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to ...
3
votes
1answer
92 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. ...
3
votes
1answer
683 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 ...
3
votes
1answer
231 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 ...
3
votes
1answer
211 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
1answer
207 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
3
votes
1answer
65 views

Generalized operators for programming languages

After asking this question on stackoverflow, it has changed slightly. Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that ...
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
952 views

Does PETSc really give speedup?

I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and ...
2
votes
1answer
200 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 &...
2
votes
1answer
39 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{...
2
votes
1answer
152 views

LU decomposition with pivoting

I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero. How to solve this problem? Iterational methods are ...
2
votes
1answer
793 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 ...
2
votes
1answer
120 views

Linear equation solving with special sparse coefficient matrix

Given a linear equation system of $n$ equations with unknowns $a_1,a_2,...,a_n\in [0,1]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ ...
2
votes
1answer
1k views

How to solve a Simple Linear Equation using a binary tree data structure

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so: ...
2
votes
1answer
41 views

Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.
2
votes
1answer
28 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$...
2
votes
1answer
13 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. ...
2
votes
1answer
62 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 ...
2
votes
1answer
718 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 ...
2
votes
1answer
317 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
253 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 ...
2
votes
1answer
1k views

Power method to calculate eigenvectors

I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, ...
2
votes
1answer
27 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
37 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 ...
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
2answers
417 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 ...
2
votes
1answer
82 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 ...
2
votes
1answer
42 views

Subspace clustering with random transformation

One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-...
2
votes
1answer
234 views

What are the drawbacks of using an algorithm that is not backwards stable?

(This question might be legitimately crossposted to stackoverflow or mathoverflow or programming StackExchanges.) Preface I'm reading this paper on solving linear systems of equations ...
2
votes
0answers
27 views

Calculating diagonal of inverse of sparse band-like matrix

I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is: $$H=(N-I)N_{dg}^{-1}$$ Where $N_{dg}$ is a diagonal ...
2
votes
0answers
39 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 ...
2
votes
0answers
45 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}...
2
votes
0answers
65 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' \...
2
votes
0answers
77 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 ...
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 ...
2
votes
0answers
41 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 $...