1
$\begingroup$

I am working on an application which consists of cross-roads and roads that connects them. In my design, I am using graph signal processing to estimate the importance of the roads which means edge weights in the Adjacency Matrix. I have the graph signal which consists of number of cars at every minute. I also know the graph topology(which road is connected to which cross road). With the information I have, I am trying to estimate the Adjacency Matrix using the following optimization problem which uses "Sparse Vector Autoregressive Estimation". I saw this method in a paper and thought maybe it can be used in my application as well.

\begin{align} \hat R_1 &= \arg\min_{R_1} \frac12 \sum_{k=M}^{K-1} \left\| x[k] - \sum_{i=1}^M R_i x[k-i] \right\|_2^2 + \lambda_1 \left\| \operatorname{vec}(R_1) \right\|_1&//&\text{With $M=1$}\\ &= \arg\min_{R_1} \frac12 \sum_{k=1}^{K-1} \left\| x[k] - R_1 x[k-1] \right\|_2^2 + \lambda_1 \left\| \operatorname{vec}(R_1) \right\|_1 \end{align}

$R_1$ estimate can be thought as "Adjacency Matrix" according to paper and $X$s are the graph signals we have. I know that this problem can be solved using "$l_1$-regularized least squares" like Lasso Regression. The problem that arrives is the result will be the Adjacency Matrix that also contains edge weights that aren't supposed to be in the model because there are no roads existing.

  • How should I solve this issue?
  • Should I add this as a constraint?

I don't have much experience regarding to optimization. Therefore, any suggestion would be very helpful. Regardless of this problem, any ideas how can I find the edge weights with the help of the information I have would be great.

Improve this question
$\endgroup$
7
  • $\begingroup$ please cite the paper and explain why you think this estimator (?) is appropriate for your problem. Also, explain why you have a $\sum$ from $i=1$ to $1$, that's confusing, to say the least. (I've converted the formula to in-line Latex, so it's easier to edit within the question.) If there's really only one summand here, you can write out your $\|\ldots\|_2^2$ and directly write it out – just a quadratic form :) $\endgroup$
    – Marcus Müller
    Aug 10, 2022 at 10:45
  • $\begingroup$ thanks for the comments and latex form. Here is the link from the paper "ieeexplore.ieee.org/document/7179022". According to this paper I take M=1 for simplicity. I think the estimator may(!) work because I think that every signal on every cross road is related to each other. Autoregressive Process idea can be a good start. I hope I explained myself better right now. $\endgroup$
    – Giray Salgır
    Aug 10, 2022 at 13:51
  • $\begingroup$ Something's not completely right about $\sum_{K=M}^{K-1}$: How can $K$ run from $M$ to itself minus one? $\endgroup$
    – Marcus Müller
    Aug 10, 2022 at 14:31
  • $\begingroup$ ah found it in the original paper, typo, fixing that. $\endgroup$
    – Marcus Müller
    Aug 10, 2022 at 14:31
  • $\begingroup$ The problem for me is to solve this optimization problem when there is a sum operation involved. I found that using proximal gradient descent, also mentioned in the paper, it can be solved. However, we have a sum operation therefore, I quite dont understand how should I apply this method to the optimization problem. $\endgroup$
    – Giray Salgır
    Aug 10, 2022 at 14:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.