Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
13 views

trying to solve linear equetion system above %Z11

give this system linear above Z11 10=(3a^2-b)x-2y by=2 find all the solutions to the linear system I am tried to figure out how to solve something like that. I know how to solve a linear equation and ...
2
votes
2answers
37 views

How to setup the Bellman Equation as a linear system of equation

I was watching a video on Reinforcement Learning by Andrew Ng, and at about minute 23 of the video he mentions that we can represent the Bellman equation as a linear system of equations. I am talking ...
10
votes
1answer
1k views

Why is the probability of a false positive not 0 for Freivald's Algorithm?

Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $n \times n$-matrices $A$ and $B$ yields a given matrix $C$ (i.e. $AB = C$). The way this task is ...
2
votes
1answer
68 views

Better way to decide if a set is a pure simplicial complex

Setup I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex. A pure simplicial complex is a set where all facets have the same degree, a ...
1
vote
1answer
46 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 ...
0
votes
0answers
14 views

Calculating the shortest vector between a vector and a truncated cone

I am trying to understand a certain implementation of calculating the shortest vector between a vector and a truncated cone in 3D. The original idea is introduced in this paper. So if we have two ...
1
vote
2answers
88 views

Fast computing of a matrix power for large integer values in C++

I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix. My objective is to compute the power of the squared matrix ...
1
vote
0answers
30 views

Least probability of collisions using rgb as a hash map

I need to rewrite a short utility library, to get it working with the Brave browser (My actual question isn't about brave per se.) canvas-color-tracker - example of it being used and src/index.js is ...
2
votes
1answer
42 views

Why is CNOT the only non-trivial reversible gate for two input bits?

The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function: $$ 00 \to 00 \\ 01 \to 01 \\ 10 \to ...
1
vote
1answer
54 views

solve a rational equation as fast as possible

I would like to find the first positive solution(if there is one) to this equation: $$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$ The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+...
0
votes
0answers
37 views

Choosing unsupervised learning algorithm for analyzing the spectrum of a linear operator

I am a theoretical physicist, and new to CS.stackexchange, and have a little knowledge of CS, and in Machine Learning (only some general stuff). In physics we often analyze the spectrum of linear ...
0
votes
0answers
35 views

Coordinate descent for Lasso, Question about algorithm

I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking ...
8
votes
2answers
1k 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 ...
1
vote
0answers
51 views

Express polynomial as sum of two lower-degree polynomials, modulo another

Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that $$p(x) \equiv r_1(x) x^...
0
votes
1answer
21 views

Designing less than and less than or equal operators for Map with value being a Set

I am trying to come up with less than and less than or equals operators for a Map where values are Sets. These are the hints I was able to get from the Professor. ...
0
votes
1answer
42 views

fastest way to identify “singular row” of a matrix

Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which ...
2
votes
0answers
56 views

Verifying a matrix is Copositive

A symmetric matrix $A\in \Bbb{R}^{n\times n}$ is copositive if for every vector $x\in\Bbb{R}^n$ with non-negative entries, we have $$x^TAx \ge 0.$$ What are known methods to check if a specific matrix ...
2
votes
1answer
63 views

Is a system of equations derived from mutually recursive ADTs always uniquely solvable?

After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer ...
2
votes
1answer
43 views

Understanding the coefficient matrix of Hermite Interpolation

I was not sure whether this is a computer science question or a math question, so I posted it here, hope that it is alright. I am trying to learn the technique of Hermite interpolation. I do ...
12
votes
4answers
7k 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 ...
0
votes
0answers
26 views

What is the name of the following linear solver

I am trying to understand Jos Stam's method for simulating stable fluids. Here on page 21 he explain that he want to solve the following linear system: ...
1
vote
1answer
52 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 ...
0
votes
0answers
31 views

Let M be a k × n random matrix with iid entries such that

$M$ is a $k × n$ random matrix with iid entries such that $P(m_{i,j} = +1) = P(m_{i,j} = −1) = 0.5.$ Let $k = O({1\over \epsilon^l})$ for some constant $l$. $v ∈ R_n$ is a fixed vector. Does a ...
4
votes
1answer
48 views

Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
0
votes
0answers
34 views

Why is the weight matrix diagonal in weighted least squares regression?

I was going through the theory for weighted least-squares fitting and I understood its basic underlying concepts, but I couldn't understand why exactly do we keep the weights as a diagonal matrix ...
2
votes
0answers
43 views

Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
3
votes
3answers
646 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 ...
6
votes
1answer
368 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 ...
1
vote
0answers
18 views

N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
1
vote
0answers
27 views

Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
1
vote
1answer
105 views

How does the sweep line algorithm check for intersection using vector cross product?

I am trying my best to understand the sweep-line algorithm to find line intersections. I have understood most of the intuition except how it is calculating the intersection between 2 line segments ...
6
votes
2answers
450 views

Testing whether a determinant polynomial is identically zero

Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots ...
0
votes
1answer
102 views

When does Gaussian elimination solve exact 1-in-3 SAT?

Terms: A literal is a variable or its negation. A clause is a set of literals. An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
0
votes
0answers
42 views

Computing structure tensors

As far as I understand, the structure tensor is: $$ M = \sum_{(x,y) \in W} \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix} = \begin{bmatrix} \sum_{(x,y) \in W} I_x^2 & \...
1
vote
1answer
39 views

Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct. Question: What would be the complexity of its inversion? On the ...
1
vote
1answer
18 views

Math behind Multi-class linear discriminate analysis (LDA)

I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction. So I understand for the algorithm to calculate for $k$ projection vector(s) you need to ...
3
votes
1answer
114 views

Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
1
vote
0answers
27 views

Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
3
votes
0answers
63 views

Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $...
0
votes
1answer
49 views

Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers : $ \\ D = \{ D_1, D_2, ..., D_n\}$ and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
2
votes
2answers
797 views

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...
3
votes
2answers
958 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 ...
15
votes
6answers
7k views

What parts of linear algebra are used in computer science?

I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For ...
1
vote
0answers
19 views

Are there practical usage of determinants in numerical simulation?

I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-...
1
vote
0answers
44 views

What is the complexity of finding e^(A) for a Hermitian matrix A?

If A is a hermitian matrix of size NxN .What is the order of no. of steps required to compute e^(A).How to prove it?
1
vote
0answers
21 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
36 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
31 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
15 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
63 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
2 3 4 5