Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 views

Kalman Filter - Dynamic System

Given the two equations below $$ \begin{aligned} 300x + 400y &= 700 \\ 100x + 133y &= 233 \end{aligned}$$ how can one find a solution for those equations using Kalman filter (and suppose the ...
2
votes
0answers
34 views

Bound on the number of signed sums of a non-zero vector that can all equal zero

Let $u$ be a real vector of $m$ entries, and $A$ be a $\pm 1$ matrix of dimension $N\times m$, and real rank $\operatorname{rank}(A) = r$. What are some conditions on $A$ (e.g. in terms of its rank $r$...
0
votes
1answer
22 views

can similarity transformation be linear transformation?

Learning Computer Graphics - Can similarity transformation be linear transformation? Similarity T is a rigid transformation (translation and rotations) with uniform scaling. so I guess a similarity ...
2
votes
1answer
44 views

What is this linear optimization problem?

Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$. Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
0
votes
0answers
25 views

How to eliminate « a priori » all vectors in a list of vectors whose scalar product with a given vector is zero without calculating the product

How to eliminate « a priori » all vectors in a list of vectors, whose scalar product with a given vector is zero, without actually calculating the product ? One solution would be to store the ...
0
votes
0answers
41 views

Recommendations on where to learn and practice linear programming?

[CLOSED] Thanks! I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts. So do you have any recommendations of materials to learn or practice Linear ...
0
votes
1answer
24 views

Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
2
votes
0answers
25 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
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
2answers
92 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 ...
0
votes
0answers
17 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
121 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
47 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 ...
0
votes
0answers
38 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 ...
1
vote
1answer
56 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
45 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 ...
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
22 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
43 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
72 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
66 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
48 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 ...
0
votes
0answers
30 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: ...
4
votes
1answer
54 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
54 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
1answer
85 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 ...
2
votes
0answers
46 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)$ ...
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
141 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 ...
0
votes
1answer
120 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
43 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
41 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
20 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
147 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 $...
2
votes
2answers
885 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 ...
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 ...
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
45 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
68 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
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 ...
1
vote
0answers
58 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
2
votes
0answers
97 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 ...

1
2 3 4 5