Questions tagged [least-squares]
The least-squares tag has no usage guidance.
44 questions
0
votes
1
answer
77
views
Least squares cross product equations
I've tried, unsuccessfully, to either solve or find a solution to something along lines of:
find $\bar{a}$, $\bar{b}$ nearby to some initial guess that satisfies $\bar{c} = \bar{a} \times \bar{b}$.
...
- 101
1
vote
1
answer
132
views
Chebyshev approximation via iterated weighted least squares fits
I have the task of finding a Chebyshev approximation for a time-series; I want to check different types of functions, e.g. polynomials, rational functions, harmonics, etc.
I know that the Remez ...
- 13.2k
2
votes
1
answer
128
views
Eigenvalue analysis of $X^T (XX^T + \mathrm{Id})^{-1} X$ for $X$ iid random matrix
Consider the following quantity
$$X^T (XX^T + \mathrm{Id})^{-1} X,$$
where $X \in \mathbb{R}^{m\times n}$ is a iid random matrix with 0 mean and finite variance.
The empiric covariance matrix ${X^T X}$...
- 2,306
0
votes
0
answers
105
views
Weighted least squares regression: Iterative modeling of variance
In chemical analysis, the instrument's signal are plotted as a function of chemical concentration. In general, higher the concentration higher is the response and the relationship is linear. At ...
- 879
1
vote
0
answers
36
views
Weighted least squares with matrices as unknowns
Let $M \in \mathbb{R}^{m \times n}$. Let $S \in \mathbb{R}^{m \times N_t}, U \in \mathbb{R}^{n \times N_t}$, with $ N_t \gg m,n$.
Moreover, $\epsilon = S - M U$, with $\epsilon$ zero mean white noise ...
- 123
1
vote
0
answers
32
views
Weighted Least squares with Multiple Unknowns and Iterations
I am currently working on a problem involving the minimization of the $\chi^2$ deviation between a model matrix ($C_\text{model}$) and a measured matrix ($C_\text{measured}$). by finding the best-fit ...
- 11
1
vote
0
answers
180
views
Least square with Frobenius norm regularization
$$
\begin{align} f_i &= \operatorname*{argmin}_f \| Af - d \| ^2_{l2} + λ \| P_X(f) - L_r(P_X(f_{i-1})) \|_F^2 \\[8pt] &=M_4^{-1}(A^Hd+\lambda P_X^*(L_r(P_X(f_{i-1})))) \end{align}
$$
where
$$
...
- 11
1
vote
1
answer
176
views
Symmetric linear least-squares solution ${\bf X} {\bf A} = {\bf B}$
Given the wide matrices ${\bf A} \in {\Bbb R}^{n \times m}$ and ${\bf B} \in {\Bbb R}^{p \times m} $, where $m > n > p$, form an overdetermined linear system in ${\bf X} \in {\Bbb R}^{p \times n}...
- 11
0
votes
1
answer
141
views
Least square error problem ill conditioning
I am trying to understand why I am getting an almost singular matrix in a problem I have.
The problem is a simple as
$$
\min_{X \in \mathbb{R}^{m,n}} \left\lVert AX - B \right\rVert_F^2
$$
Obvioulsy ...
- 115
1
vote
1
answer
180
views
Shape, shift and scaling retrieval of a sampled function
Let $f(x)$ be some unknown continuous square-integrable function defined on the interval $[0,1]$.
Suppose we have $i=1,...,n$ samples $f_i$ of $f$ of the following form:
$$f_i(x)=a_i*f(x+b_i)+c_i$$
...
- 230
0
votes
1
answer
110
views
Trigonometry/spherical angles/minimum-least-squares [closed]
An issue from 3D tessellated geometry: Find the direction vector of a plane that minimizes the silhouette of a set of triangles. To say it another way, find the direction vector that is most ...
- 103
1
vote
0
answers
66
views
Least squares regression with nonnegative error
I'm looking for algorithms to solve a special quadratic programming problem, but I don't know its name or related keywords. Can anyone give me some clues? The problem reads
\begin{equation}
{\min}_x \...
- 11
1
vote
3
answers
345
views
How to optimize for the best fit nonuniform-scale-rotation to a given 3×3 matrix?
Given a matrix $L\in \mathbb{R}^{3 \times 3}$, I'm looking for a method to find the closest (in a least squares sense) product of a non-uniform scaling matrix and a rotation matrix:
$$
\min_{s\in\...
- 723
4
votes
1
answer
172
views
Least squares problem with left and right unknowns
For $i=1,...,n$, let $b_i$ be a scalar and $A_i$ be an $k\times l$ matrix. Is there a closed form solution for the following problem assuming $n>k+l$?
$$\min_{x\in \mathbb{R}^k ,y\in \mathbb{R}^l} \...
- 230
2
votes
0
answers
72
views
Under what conditions is the least-squares approximation bounded with the same Lipschitz gradient constants?
Let $f(x):\mathbb{R}^K\Longrightarrow \mathbb{R}^L$ denote a multivariate continuously differentiable function. All the partial derivatives of $f$ (all its Jacobian elements) are bounded from above ...
- 21
1
vote
0
answers
226
views
Solution that minimizes the sum of squared errors, with quadratic constraints
Given symmetric and positive definite $n \times n$ (real) matrices $A_1, \dots, A_m$ and $b_1, \dots, b_m \in {\Bbb R}^{n}$, I am trying to find the solution with the least sum of squared errors of ...
- 11
2
votes
0
answers
122
views
Given normal equations with nonnegative solution, is there always a subsystem with nonnegative solution?
Given a system of normal equations $A^TAx=A^Tb$ where $A^TA$ is $n\times n$,
what I call the $i$th subsystem is the linear system of size $n-1\times n-1$ where the $i$th column of $A$ has been removed....
- 29
1
vote
0
answers
34
views
Minimum eigenvalue of normal matrix with polynomial basis
For each $n\in \mathbb{N}\cup\{0\}$, let $x_n(t)=\frac{t^n}{n!}$ for all $t\in [0,1]$. As the functions $X_N=(x_0 ,\ldots, x_N)$ are linearly independent, the matrix
$
\int_0^1 X_N(t)^\top X_N(t)\,\...
- 503
20
votes
4
answers
5k
views
Is the pseudoinverse the same as least squares with regularization?
Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. ...
- 501
3
votes
1
answer
379
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
- 6,853
1
vote
2
answers
202
views
Robust estimation of $Ax=b$
Problem setting :
$ \underset{x}{\text{min}} \|Ax-b\|$, where $A \in \mathcal{R}^{m \times n}, m\gg n $, full rank.
L1 loss is used for robust estimation using IRLS. The corresponding equation to ...
- 21
1
vote
1
answer
166
views
Understanding the Time Delay of Arrival trilateration algorithm
I'm trying to algorithmically solve the Time Delay of Arrival problem as part of some mathematics research. The problem is as follows:
Given the location of three receivers in a plane (A, B, and C), ...
- 111
2
votes
2
answers
106
views
Non-parametric regression and curvature
Given a finite set of points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ in the plane, Linear Regression tells us how to find the straight line "$y=a+bx$" best approximating the given points, in the ...
- 2,263
1
vote
3
answers
90
views
RKHS/non-parametric regression with missing response values
I am interested in doing RKHS regression with missing response variables.
Given input-output pairs $(x_i,y_i)$, I want to estimate a function $f(\cdot)$ as follows
\begin{equation}f(x)\approx u(x)=\...
- 41
2
votes
1
answer
301
views
Minimise $\sum_i \begin{Vmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{Vmatrix}$
Consider column vectors $\boldsymbol{z}_i$, $\quad i=1,\dots,n$.
Each $\boldsymbol{z}_i$ has $j$ elements and can be expressed as $\boldsymbol{z}_i = \begin{bmatrix} \boldsymbol{x}_i \\ \boldsymbol{y}...
7
votes
2
answers
1k
views
Symmetric linear least-squares solution
Given tall matrices $A$ and $Y$ and the following overdetermined linear system in square matrix $X$
$$AX=Y$$
is there an explicit formula for the least-squares solution if $X$ is constrained to be ...
- 223
0
votes
1
answer
950
views
How to determine the damping factor in Levenberg-Marquardt?
From the algorithm, we can see that it tries different damping factor until it gets a good one by the error. Is the damping factor related to the eigenvalues of the Hessian matrix?
2
votes
0
answers
37
views
Difference Between Total Least Squares Plane and Plane Orthogonal to Principal Axis of Inertia Tensor
Given a finite set $P$ of points in $\mathbb{E}^3$ , one can calculate an approximating plane either as the solution of a Total Least Squares problem or by interpreting the problem physically, ...
- 13.2k
1
vote
1
answer
170
views
Minimization Proof of Conditioning on Gaussian is Gaussian
It is well known that $E[X|X+Y]$ is Gaussian if both $X$ and $Y$ are, and the result can be derived using standard density arguments. However, how can one prove it by only resulting to optimization ...
- 5,407
1
vote
0
answers
137
views
Choice of residual function for least squares error minimization
Good morning,
I have the a set of data $(\sigma,D,\alpha_0)_i$, $i=1...n$ data.
I want to determine two parameters $K_{IC}$, $C_f$ in the basic equation given as
$K_{IC} = \sigma \sqrt{D} k_0(\...
- 11
2
votes
2
answers
504
views
In practice, what's the fastest method to find a least square solution rather than using SVD decompostion?
I'm working on a real-time implementation of Lucas-Kanade for optical flow. However, the SVD decomposition to do achieve the least square method to reduce the error seems to take too much time.
A ...
- 121
8
votes
3
answers
372
views
Regularized linear vs. RKHS-regression
I'm studying the difference between regularization in RKHS regression and linear regression, but I have a hard time grasping the crucial difference between the two.
Given input-output pairs $(x_i,y_i)...
- 41
5
votes
1
answer
315
views
Rank-constrained least-squares solution of the Sylvester matrix equation
For the Sylvester matrix equation $AX+XB=C$, I want to find the least-squares solution $X$ via
$$\begin{array}{ll} \text{minimize} & \| AX + XB - C \|_{\text{F}}^2\\ \text{subject to} & \mbox{...
- 191
4
votes
1
answer
455
views
Least square solution to $AXB+CXD=E$
I am trying to find the least-squares solution $X$ of the following matrix equation
$$AXB+CXD=E$$
Of course, I know that this equation can be written in the form
$$(B^T \otimes A+D^T \otimes C) \...
- 191
3
votes
2
answers
386
views
Standard solution to semidefinite program [closed]
I have an optimization problem of the following form
$$\text{minimize} \,\|Qa-b\|_2 \quad \text{ subject to } Q \succeq 0$$
where $a,b \in \mathbb{R}^n$ are given and the $n \times n$ square matrix ...
- 153
2
votes
1
answer
191
views
Reconstruct matrix given all differences of neighbors
We have an unknown $m\times n$ matrix $X=(x_{ij})_{i=1,j=1}^{m,n}$. Assume we are given measurements of the differences
$$x_{i,j+1}-x_{i,j}$$
and
$$x_{i+1,j}-x_{i,j}$$ for all $(i,j)\in \{1,\...
- 398
9
votes
1
answer
21k
views
Gauss-Newton vs gradient descent vs Levenberg-Marquadt for least squared method
I need to clarify some idea I have in my mind about linear and non-linear regressions. Whatever I know about this topic comes from the book of Taylor "Introduction to error analysis": a set ...
- 203
0
votes
0
answers
76
views
Why is ideal wavelet selection a least-squares estimate?
In their classic paper "Ideal spatial adaptation by wavelet shrinkage" (http://biomet.oxfordjournals.org/content/81/3/425.short?rss=1&ssource=mfr), Donoho and Johnstone make the following ...
- 121
1
vote
1
answer
138
views
MSE of measurable function is still conditional expectation
Motivation
Then the usual stochastic filtering problem says that:
$$
\operatorname{argmin}_{Z \in L^2(\mathscr{G}_t)}\,\mathbb{E}[(Y_t-Z_t)^2],
$$
where $\mathscr{G}_t$ is the $\sigma$-algebra ...
- 5,407
1
vote
1
answer
205
views
Least squares problem with constrained solution [closed]
If $a_{m\times 1}$ and $Q_{m\times n}$ ($m<n $) are known, and we know every element of $b$ is between $[-1\ \ 1]$, how to determine $b$ to minimize $\|a+Qb\|_2$?
- 29
2
votes
1
answer
396
views
How to force least squares solution matrix to be diagonal? [closed]
I have the following matrix equation
$$AX=B$$
given $8 \times 3$ matrices $A$ and $B$. $X$ is a $3 \times 3$ diagonal matrix whose main diagonal contains the $3$ unknowns.
Whenever I solve for $X$ ...
- 21
7
votes
1
answer
227
views
Least-squares solution of systems of Sylvester equations
The Sylvester equation $AX+XB=C$ has been studied quite a lot and there are known algorithms for solving it.
But has the situation where (an over-determined) system of equations $A_{i}X+XB_{i}=C_{i}$ ...
- 6,962
0
votes
2
answers
320
views
Solving sparse linear least squares or a positive definite 5-band matrix system fast
I want to quickly solve the following linear least-squares problem
$$\min_{x \in \mathbb{R}^n} \left\| A x - b \right\|_2^2$$
with a special sparse structure where each row in $A$ has only up to $4$ ...
- 101
3
votes
1
answer
3k
views
How do I optimize over (or take derivative wrt) a square diagonal matrix?
I would like to solve the following optimization problem in $k$-vector $w_i$
$$ \min_{w_i} \quad \left\|P_i - X \mbox{diag} (w_i) Y^T \right\|_F^2 $$
where $P_i$ is a $6 \times 6$ matrix, $X$ and $Y$ ...
- 33