2022 Developer Survey is open! Take survey.

Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

Fourier Dimension of Boolean functions

I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
user avatar
1 vote
2 answers
152 views

Clarification regarding linear boolean functions!

I am a little confused when it comes to linear boolean functions. According to this post: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
user avatar
  • 13
1 vote
1 answer
29 views

Complexity of finding $d$ largest eigenvectors of a symmetric matrix

I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
user avatar
0 votes
1 answer
22 views

Getting a "sub-polytope" of a concave d-dimensional polytope, given some one dimensional inequality

The question will be hard to understand without an example, so let's given an example first: Let's say I have a 2 dimensional concave polytope, defined by a circular sequence of its vertices: $(0,0), (...
user avatar
1 vote
0 answers
53 views

Is there an alternative method to using Gaussian elimination in order to solve 3-XORSAT

I have a large system of $3$-$XORSAT$ constraints (i.e. up to $3$ variables per constraint) and this can be represented in matrix form as a linear algebra problem $Ax=b$ $mod$ $2$. Solvability (i.e. ...
user avatar
  • 11
1 vote
1 answer
18 views

(Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory [closed]

The Weight Distribution / Subspace Weights Problem in coding theory is defined as this: Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$ Question: Is there a set of $k$ columns of $...
user avatar
0 votes
1 answer
29 views

Finding a $d$-dimensional hyperplane containing $n$ given points

I'm currently trying to find the equation of the $d$-dimensional hyperplane which includes $n$ given points, where $n \ge d$. Theoretically, it isn't hard - the $d$-dimensional hyperplane is ...
user avatar
1 vote
0 answers
20 views

Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
user avatar
0 votes
0 answers
21 views

Is one set of vectors constructed by another set of vectors?

Let there be given set of vectors $V = \{v_1, v_2, ..., v_n\}$ and set of vectors $S = \{s_1, s_2, ..., s_k\}$ where $n > k$. The set of vectors $V$ can be constructed by $S$ if the vectors in $V$ ...
user avatar
0 votes
0 answers
42 views

Which of these algorithms will involve the least amount of math?

I'm taking an algorithms class for my computer science degree, and one of the requirements is to research and present 3 different algorithms. The only problem: linear algebra wasn't a prerequisite to ...
user avatar
0 votes
0 answers
42 views

Finding a set of 9 integers that minimize an error function

I have an algorithm that takes a 3d triangle PMN(which is constructed from running a function that converts per-vertex UV coordinates to a PMN triangle) and P' which is a randomly chosen 3D point that ...
user avatar
  • 101
5 votes
0 answers
94 views

Optimization problem with discrete and continuous components

Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between ...
user avatar
  • 265
0 votes
0 answers
25 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 ...
user avatar
3 votes
0 answers
41 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$...
user avatar
  • 961
0 votes
1 answer
33 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 ...
user avatar
2 votes
1 answer
48 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-...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
43 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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 31
2 votes
0 answers
31 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 ...
user avatar
10 votes
1 answer
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 ...
user avatar
  • 103
2 votes
2 answers
223 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 ...
user avatar
  • 121
0 votes
0 answers
21 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 ...
user avatar
  • 1
1 vote
2 answers
155 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 ...
user avatar
1 vote
0 answers
31 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 ...
user avatar
  • 11
2 votes
1 answer
51 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 101
1 vote
1 answer
62 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+...
user avatar
0 votes
0 answers
73 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 ...
user avatar
1 vote
0 answers
56 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^...
user avatar
  • 140k
0 votes
1 answer
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. ...
user avatar
  • 129
0 votes
1 answer
53 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 ...
user avatar
  • 125
2 votes
0 answers
83 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 ...
user avatar
2 votes
1 answer
70 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 ...
user avatar
2 votes
1 answer
82 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 ...
user avatar
4 votes
1 answer
79 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$ ...
user avatar
1 vote
1 answer
114 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 ...
user avatar
2 votes
1 answer
115 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 ...
user avatar
  • 133
2 votes
0 answers
48 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)$ ...
user avatar
1 vote
0 answers
22 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 ...
user avatar
  • 175
1 vote
0 answers
29 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 ...
user avatar
  • 111
1 vote
1 answer
185 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 ...
user avatar
  • 215
0 votes
1 answer
151 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 ...
user avatar
0 votes
0 answers
44 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 & \...
user avatar
  • 1
1 vote
1 answer
45 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 ...
user avatar
  • 123
1 vote
1 answer
29 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 ...
user avatar
3 votes
1 answer
170 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 ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
3 votes
0 answers
67 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 $...
user avatar
2 votes
2 answers
942 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 ...
user avatar

1
2 3 4 5